|
题目
给你一个由 '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
分析
这是一道典型的深度优先算法题，?也是一道高频题，非常有代表性，虽然简单但还是需要为它写?一篇文章。
深度优先算法是一直往一个方向探索直到失败，然后回到上一个节点往另外一个方向探索。
深度优先放在这道题的思路是遍历每个格子，当遇到1时就以这个1为起点，向上下左右四个方向探索，直到把从这个格子出发能到达?的所有1找出来，一次探索就是一个?岛屿。
另外一个问题就是如何避免重复探索呢? 可以将每次探索后的格子值改为0，这样就避免了?重复。
代码
class Solution {
public int numIslands(char[][] grid) {
int res = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j] != '1'){
continue;
}
dfs(i, j, grid);
res ++;
}
}
return res;
}
void dfs(int i, int j, char[][] grid) {
if(grid[i][j] == '0'){
return;
}
grid[i][j] = '0';
if(i+1 < grid.length && grid[i+1][j] == '1'){
dfs(i+1, j, grid);
}
if(j+1 < grid[0].length && grid[i][j+1] == '1'){
dfs(i, j+1, grid);
}
if(i-1 >= 0 && grid[i-1][j] == '1'){
dfs(i-1, j, grid);
}
if(j-1 >=0 && grid[i][j-1] == '1'){
dfs(i, j-1, grid);
}
}
}
结果
关注个人微信公众号：肌肉码农，回复“好友”讨论问题。
?
|