-
Notifications
You must be signed in to change notification settings - Fork 1
/
number-of-islands.php
50 lines (43 loc) · 1.05 KB
/
number-of-islands.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<?php
class Solution
{
/**
* @param Integer[][] $grid
* @return Integer
*/
public function numIslands($grid)
{
$row = count($grid);
$column = count($grid[0]);
$count = 0;
for ($i = 0; $i < $row; $i++) {
for ($j = 0; $j < $column; $j++) {
// 简化、逻辑清晰:只要是 1,就 count++
if ($grid[$i][$j] == '1') {
$this->dfs($grid, $i, $j);
$count++;
}
}
}
return $count;
}
protected function dfs(&$grid, $i, $j)
{
if ($grid[$i][$j] != '1') {
return ;
}
// 省去了标志数组
$grid[$i][$j] = '2';
$this->dfs($grid, $i, $j-1);
$this->dfs($grid, $i, $j+1);
$this->dfs($grid, $i+1, $j);
$this->dfs($grid, $i-1, $j);
}
}
$grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
];
echo (new Solution())->numIslands($grid);