hot100-47岛屿数量

一、题目

由 1 和 0组成的二维网格，计算网格中岛屿的数量。

岛屿总是被水包围，并且每个岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

二、思路

1、深度优先搜索DFS：遍历网格，如果当前格子是'1'，说明找到了一个新的岛屿。计数+1，并调用 dfs递归把上下左右淹没整个岛屿（把相连的 '1' 改为 '0'）

2、广度优先遍历BFS：定义一个二维布尔数组 visited 和队列queue。遇到未访问的 '1' 启动搜索，一层层向外扩展，将整个岛屿的所有格子标记为已访问。（在BFS中处理队列中的坐标的四周坐标，标记已访问）

三、代码

1）深度优先搜索 DFS

class Solution { public int numIslands(char[][] grid) { int count = 0; int m = grid.length, n = grid[0].length; for(int i = 0;i<m;i++){ for(int j = 0; j<n;j++){ if(grid[i][j] == '1'){ count++; dfs(grid,i,j); } } } return count; } public void dfs(char[][] grid,int i,int j){ int m = grid.length, n=grid[0].length; if(i <0 || i>=m || j<0 || j>=n || grid[i][j] == '0') return ; grid[i][j] = '0'; dfs(grid,i-1,j); dfs(grid,i+1,j); dfs(grid,i,j-1); dfs(grid,i,j+1); } }

2）广度优先搜索 BFS

class Solution { int res = 0; int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}}; boolean[][] visited; public int numIslands(char[][] grid) { int m = grid.length,n = grid[0].length; visited = new boolean[m][n]; for(int i = 0;i<m;i++){ for(int j = 0;j<n;j++){ if(grid[i][j] == '1' && !visited[i][j]){ bfs(grid,i,j); res++; } } } return res; } LinkedList<int[]> queue = new LinkedList<>(); public void bfs(char[][] grid,int i,int j){ int m = grid.length, n = grid[0].length; queue.offer(new int[] {i,j}); while(!queue.isEmpty()){ int size = queue.size(); for(int num = 0; num < size; num++){ int[] node = queue.poll(); for(int d = 0;d<4;d++){ int nodeX = node[0]+dir[d][0]; int nodeY = node[1]+dir[d][1]; if(nodeX<0 || nodeX>=m || nodeY<0 || nodeY>=n) continue; if(grid[nodeX][nodeY] == '1' && !visited[nodeX][nodeY]){ queue.offer(new int[] {nodeX,nodeY}); visited[nodeX][nodeY] = true; } } } } } }

四、总结

都在主函数中遍历网格，每遇到一个未处理的陆地（'1'）就计数加一，并通过搜索（DFS 或 BFS）将该陆地所属的整个岛屿全部标记为“已处理”，避免重复计数。差异在于：DFS 直接将原数组中的 '1' 改为 '0' 来标记访问，不使用额外空间；而 BFS 保留原数组不变，借助一个visited数组来记录是否访问过，仅对未访问的 '1' 进行处理。