島嶼數(shù)量
題意
給你一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格胚宦，請你計算網(wǎng)格中島嶼的數(shù)量驶睦。
島嶼總是被水包圍晨炕，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成掏愁。
此外歇由，你可以假設該網(wǎng)格的四條邊均被水包圍
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
解釋: 每座島嶼只能由水平和/或豎直方向上相鄰的陸地連接而成。
解題思路：DFS 深度優(yōu)先算法(Depth First Search)
解題代碼
class Solution {
private $isArr = [];
/**
* @param String[][] $grid
* @return Integer
*/
public function numIslands($grid) {
$num = 0;
for ($i = 0;$i < count($grid);$i++) {
for ($j = 0;$j < count($grid[$i]);$j++) {
if ($grid[$i][$j] == 1 && $this->isArr[$i][$j] != true) {
$num++;
$this->getPath($grid, $i, $j);
}
}
}
return $num;
}
private function getPath($grid, $i, $j){
if ($i < 0 || $i >= count($grid)) {
return;
}
if ($j < 0 || $j >= count($grid[$i])) {
return;
}
if ($grid[$i][$j] != 1 || $this->isArr[$i][$j] == true) {
return;
}
$this->isArr[$i][$j] = true;
$this->getPath($grid, $i - 1, $j);
$this->getPath($grid, $i + 1, $j);
$this->getPath($grid, $i, $j - 1);
$this->getPath($grid, $i, $j + 1);
}
}
測試
$arr[] = [1, 1, 1, 1, 0, 0];
$arr[] = [1, 1, 0, 1, 0, 0];
$arr[] = [1, 1, 0, 0, 1, 1];
$arr[] = [0, 0, 0, 0, 0, 1];
$arr[] = [0, 0, 0, 0, 1, 1];
print_r((new Solution())->numIslands($arr)); //輸出 2
