当前位置 博文首页 > 阳阳的博客：【leetcode.200】岛屿数量
给你一个由?'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出:?1
示例?2:输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
从网格的左上角开始，采用深度优先遍历，将与这个点连通的陆地全部遍历一遍。为了避免重复遍历，需要将遍历过的陆地进行标记。
陆地为1，水为0，遍历过的陆地为2。
假设(m，n)为网格上的任意一点，那么它的四周坐标为：
?
那么，当前思路是：
顺序遍历二维数组中的元素
? ? ? ? 比如现在选择第一个位置，即(0,0)。如果当前位置为1，则岛屿数量自增1。
? ? ? ? 接着开始访问旁边所有的点：
? ? ? ? ? ? ? ?沿着该点一直往上找，如果找到1，则将那块区域标记为2。如果不为1，则立即返回。
? ? ? ? ? ? ? ?沿着该点一直往下找，如果找到1，则将那块区域标记为2。如果不为1，则立即返回。
? ? ? ? ? ? ? ?沿着该点一直往左找，如果找到1，则将那块区域标记为2。如果不为1，则立即返回。
? ? ? ? ? ? ? ?沿着该点一直往右找，如果找到1，则将那块区域标记为2。如果不为1，则立即返回。
public class Number200 implements DFS {
// (m-1,n)
// (m,n-1) (m, n ) (m,n+1)
// (m+1,n)
char[][] map;
public int numIslands(char[][] grid) {
map = grid;
int sum = 0;
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
if (map[i][j] == '1') {
sum++;
dfs(i, j);
}
}
}
return sum;
}
private void dfs(int m, int n) {
//如果不在区域中
if (!inArea(m, n)) {
return;
}
//如果是水
if (map[m][n] == '0') {
return;
}
//如果已经遍历过
if (map[m][n] == '2') {
return;
}
//当前位置为陆地，那么设置为访问过
map[m][n] = '2';
//一直向上访问
dfs(m - 1, n);
//一直向下访问
dfs(m + 1, n);
//一直向左访问
dfs(m, n - 1);
//一直向右访问
dfs(m, n + 1);
}
//判断是否在网格中
private boolean inArea(int m, int n) {
return m >= 0 && m < map.length
&& n >= 0 && n < map[0].length;
}
public static void main(String[] args) {
char[][] map = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
int i = new Number200().numIslands(map);
System.out.println(i);
}
}
提交答案：
