岛屿数量
题干
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入
:
11110
11010
11000
00000
输出
: 1
示例 2:
输入
:
11000
11000
00100
00011
输出
: 3
分析
我们会发现这样的事： 从上到下从左往右，对于找到的‘1’， 如果是第一个找到的’1’，那么岛屿数量+1成1，如果是其他的1，如果它的上下左右都是1,那么就不改变数量。 上下左右都是0或者null，则数量++
代码
class Solution {
public int numIslands(char[][] grid
) {
if (grid
== null
|| grid
.length
== 0) {
return 0;
}
int rows
= grid
.length
;
int cols
= grid
[0].length
;
int count
= 0;
for (int i
= 0; i
< rows
; i
++) {
for (int j
= 0; j
< cols
; j
++) {
if (grid
[i
][j
] == '1') {
count
++;
dfsSearch(grid
, i
, j
, rows
, cols
);
}
}
}
return count
;
}
private void dfsSearch(char[][] grid
, int i
, int j
, int rows
, int cols
) {
if (i
< 0 || i
>= rows
|| j
< 0 || j
>= cols
) {
return;
}
if (grid
[i
][j
] != '1') {
return;
}
grid
[i
][j
] = '0';
dfsSearch(grid
, i
+ 1, j
, rows
, cols
);
dfsSearch(grid
, i
- 1, j
, rows
, cols
);
dfsSearch(grid
, i
, j
+ 1, rows
, cols
);
dfsSearch(grid
, i
, j
- 1, rows
, cols
);
}
}
总结
查看别人的算法说这就是一个深度优先广度优先的问题，但是我只是想到了这道题的的解法还没有想到深度优先相关
