一、题目
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
二、示例
示例 1：
【输入】grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
【输出】1
示例 2：
【输入】grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
【输出】3
提示：
- m == grid.length
- n == grid[i].length
-
1<= m, n <=300 - grid[i][j] 的值为 '
0' 或 '1'
三、解题思路
根据题目描述，每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。那么我们就可以通过对某个格子的上方向、下方向、左方向和右方向进行遍历，来判断每个岛屿了。
在遍历过程中，由于我们是针对每一个格子都进行上下左右四个方向的遍历，所以，会出现重复遍历相同格子的情况发生，那么我们就需要进行如下的判断逻辑防止这种情况发生了：
【判断1】遍历的格子不能越界；
【判断2】遍历到的格子如果是1，才继续遍历，否则终止该方向的遍历；
【判断3】只要遍历到的格子是1，则将该格子值变为0（防止重复遍历值为1的格子）；
以上就是判断一个岛屿的方式，当我们将整个数组都遍历完毕后，就可以统计出来一共有多少的岛屿数目了。为了便于大家理解，下面我们以输入grid = [["1","1","0","0","0"],["1","1","0","0","0"], ["0","0","1","0","0"],["0","0","0","1","1"]]为例，看一下具体的操作流程是怎么样的。请见下图所示：
四、代码实现
class Solution {
int result = 0;
char[][] grid;
public int numIslands(char[][] grid) {
this.grid = grid;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(i, j);
result++;
}
}
}
return result;
}
public void dfs(int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
grid[i][j] = '0';
dfs(i - 1, j); // 向上遍历
dfs(i + 1, j); // 向下遍历
dfs(i, j - 1); // 向左遍历
dfs(i, j + 1); // 向右遍历
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论