LeetCode [中等]岛屿数量
200. 岛屿数量 - 力扣（LeetCode）
找到值为1的节点之后递归调用DFS遍历，并使用与地图数据结构相同的二维数组visited来保存该点是否访问过
深度优先遍历
public class Solution {
static int[][] dirs = {new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};
int m, n;
char[][] grid;
bool[][] visited;
public int NumIslands(char[][] grid) {
int islands = 0;
this.m = grid.Length;
this.n = grid[0].Length;
this.grid = grid;
this.visited = new bool[m][];
for (int i = 0; i < m; i++) {
this.visited[i] = new bool[n];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0' || visited[i][j]) {
continue;
}
islands++;
DFS(i, j);
}
}
return islands;
}
public void DFS(int row, int col) {
visited[row][col] = true;
foreach (int[] dir in dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == '1' && !visited[newRow][newCol]) {
DFS(newRow, newCol);
}
}
}
}
时间复杂度：O(mn)，其中 m 和 n 分别是网格 grid 的行数和列数。深度优先搜索最多需要访问每个元素一次。
空间复杂度：O(mn)，其中 m 和 n 分别是网格 grid 的行数和列数。记录每个元素是否被访问过的二维数组和递归调用栈需要 O(mn) 的空间。