LeetCode200给你一个由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]]输出3Python解法1.DFS深度优先class Solution: def numIslands(self, grid: List[List[str]]) - int: nr len(grid) if nr 0: return 0 nc len(grid[0]) num 0 for r in range(nr): for c in range(nc): if grid[r][c] 1: num 1 self.dfs(grid, r, c) return num def dfs(self, grid, r, c): grid[r][c] 0 nr, nc len(grid), len(grid[0]) for x, y in (r - 1, c), (r 1, c), (r, c - 1), (r, c 1): if 0 x nr and 0 y nc and grid[x][y] 1: self.dfs(grid, x, y)2.BFS广度优先from collections import deque class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 res 0 dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] row len(grid) col len(grid[0]) for r in range(row): for c in range(col): if grid[r][c] 1: res 1 grid[r][c] 0 q deque() q.append((r, c)) while q: x, y q.popleft() for dx, dy in dirs: nx x dx ny y dy if 0 nx row and 0 ny col and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) return resJava解法1.DFS深度优先class Solution{ public int numIslands(char[][] grid){ if(grid null || grid[0] null)return 0; int nr grid.length; int nc grid[0].length; int count 0; for(int r 0; r nr; r){ for(int c 0; c nc; c){ if(grid[r][c] 1){ count; dfs(grid, r, c, nr, nc); } } } return count; } private void dfs(char[][] grid, int x, int y, int row, int col){ if(x 0 || x row || y 0 || y col ||grid[x][y] 0)return; grid[x][y] 0; dfs(grid, x 1, y, row, col); dfs(grid, x - 1, y, row, col); dfs(grid, x, y 1, row, col); dfs(grid, x, y - 1, row, col); } }2.BFS广度优先class Solution{ //方向数组上下左右 private final int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int numIslands(char[][] grid){ if(grid null || grid.length 0)return 0; int row grid.length; int col grid[0].length; int count 0; for(int i 0; i row; i){ for(int j 0; j col; j){ if(grid[i][j] 1){ count; Queueint[] queue new LinkedList(); grid[i][j] 0; queue.add(new int[]{i, j}); while(!queue.isEmpty()){ int[] curr queue.poll(); int x curr[0], y curr[1]; //遍历四个方向 for(int[] d : dirs){ int nx x d[0]; int ny y d[1]; if(nx 0 nx row ny 0 ny col grid[nx][ny] 1){ grid[nx][ny] 0; queue.add(new int[]{nx, ny}); } } } } } } return count; } }C解法1.DFS深度优先class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int rows grid.size(); int cols grid[0].size(); int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private: void dfs(vectorvectorchar grid, int x, int y) { int rows grid.size(); int cols grid[0].size(); // 越界 或 当前是海水直接返回 if (x 0 || x rows || y 0 || y cols || grid[x][y] 0) { return; } // 标记已访问 grid[x][y] 0; // 上下左右递归 dfs(grid, x - 1, y); dfs(grid, x 1, y); dfs(grid, x, y - 1); dfs(grid, x, y 1); } };2.BFS广度优先class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int rows grid.size(); int cols grid[0].size(); // 上下左右方向数组 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; queuepairint, int q; grid[i][j] 0; q.push({i, j}); // 起点入队 while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first; int y cur.second; // 遍历四个方向 for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 nx rows ny 0 ny cols grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return count; } };深度优先 广度优先一、核心思想1. DFS 深度优先 Depth-First Search一条路走到黑走到底再回溯换分支顺序根 → 左子树一路到底 → 回退 → 右子树数据结构栈 Stack递归本质是调用栈特点先深后广适合找路径、拓扑排序、连通块、迷宫走法2. BFS 广度优先 Breadth-First Search一层一层全部遍历完再走下一层顺序根 → 同一层所有节点 → 下一层全部节点数据结构队列 Queue特点逐层扩散天然求最短路径无权图二、核心优缺点 适用场景DFS优点空间开销小只存当前路径代码递归简洁适合枚举所有可行路径、迷宫、岛屿数量、拓扑排序。 缺点不适合求最短路径递归会栈溢出深度极大时。BFS优点无权图一定得到最短路径不会深度溢出层序遍历、最短步数、最短迷宫出口首选。 缺点每层节点都要入队空间消耗更大很难记录完整路径。