AlgoPressAppearance
题目描述
https://leetcode.cn/problems/number-of-islands
给你一个由 '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的点开始，使用dfs遍历将相邻数据都标志位使用。 这样循环整个棋盘，每次遇到新1，就表示有一个岛屿，然后dfs将其相邻地区都标记为used。
参考代码
csharp
public class Solution {
private void dfs(char[][] grid, bool[,] used, int i, int j){
if(i<0 || j<0|| i == grid.Length || j == grid[0].Length || grid[i][j] == '0' || used[i,j]){
return;
}
used[i,j] = true;
//往两边扩展
dfs(grid,used,i-1,j);
dfs(grid,used,i+1,j);
dfs(grid,used,i,j+1);
dfs(grid,used,i,j-1);
}
public int NumIslands(char[][] grid) {
//遍历数组，遇到为1的开始处理连接的岛屿，并且将其标记为 used
int m = grid.Length;
int n = grid[0].Length;
bool[,] used = new bool[m,n];
int count = 0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j] == '1' && !used[i,j]){
count++;
dfs(grid,used,i,j);
}
}
}
return count;
}
}