代码随想录 200.岛屿数量

思路：

（1）题目中每座岛屿只能由水平方向和竖直方向上相邻的陆地连接而成，也就是说斜角度的连接不算。例如示例二，是三个岛屿。

（2）本题的思路是遇到一个没有遍历过的节点陆地，计数器就加1，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过，这样计数器就是最终岛屿的数量。

（3）把节点陆地所能遍历到的陆地都标记上，就可以使用DFS、BFS或并查集。

一、DFS：

1.目标是找到矩阵中“岛屿的数量”，上下左右相连的1都被认为是连续岛屿。

2.dfs方法：设目前指针指向一个岛屿中的某一个点（i,j），寻找包括此点的岛屿边界。

（1）从（i,j）向此点的上下左右（i + 1,j）、（i - 1,j）、（i,j + 1）、（i、j - 1）做深度搜索。

（2）终止条件：

——（i,j）越过矩阵边界。

——grid[i][j] = 0，表示此分支已越过岛屿边界。

（3）搜索岛屿的同时，执行grid[i][j] = '0'，即将岛屿的所有节点删除，以免之后重复搜索相同的岛屿。

3.主循环：遍历整个矩阵，当遇到grid[i][j] = '1'的时候，从此点开始做深度优先搜索dfs，岛屿数count + 1且在深度优先搜索中删除此岛屿。

4.最终返回岛屿数count即可。

附代码：

class Solution { public int numIslands(char[][] grid) { int count = 0; for(int i = 0;i < grid.length;i++){ for(int j = 0;j < grid[0].length;j++){ if(grid[i][j] == '1'){ //发现新岛屿 dfs(grid,i,j); //将整个岛屿标记为已访问(沉没整个岛屿) count++; //岛屿数量 + 1 } } } return count; } private void dfs(char[][] grid,int i,int j){ //递归终止条件（边界检查 + 遇到水/已访问的陆地） // ||操作具有短路特性，只要前面的任何一个条件为true，后面的条件就不会执行 //因此要先做边界检查，当边界检查都通过后再判断grid[i][j] // &&也有短路特性 if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){ return; } //将当前陆地标记为已访问（沉没岛屿，改为‘0’） grid[i][j] = '0'; //向四个方向递归探索 dfs(grid,i + 1,j); //下 dfs(grid,i,j + 1); //右 dfs(grid,i - 1,j); //上 dfs(grid,i,j - 1); //左 } }

二、BFS：

1.主循环和DFS类似，不同点在于搜索某岛屿边界的方法不同。

2.BFS方法：

（1）借用一个队列queue，判断队列首部节点（i,j）是否未越界且为‘1’。

——若是，则置0（删除岛屿节点），并将此节点的上下左右节点（i + 1,j）、（i - 1,j）、（i,j + 1）、（i,j - 1）加入队列。

——若不是，则跳过此节点。

（2）remove(pop)队列的首节点，直到整个队列为空，此时已经遍历完此岛屿。

附代码：

class Solution { public int numIslands(char[][] grid) { int count = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '1'){ //发现新岛屿 bfs(grid, i, j); //将整个岛屿标记为已访问（沉没整个岛屿） count++; //岛屿计数 + 1 } } } return count; } private void bfs(char[][] grid, int i, int j){ LinkedList<int[]> queue = new LinkedList<>(); //BFS队列 queue.add(new int[] { i, j }); //将起始点加入队列 while(!queue.isEmpty()){ int[] cur = queue.remove(); //取出队首节点 i = cur[0]; j = cur[1]; //检查节点是否有效且是陆地 if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') { grid[i][j] = '0'; //标记为已访问（改为水） //将四个方向的相邻节点加入到队列 queue.add(new int[] { i + 1, j }); queue.add(new int[] { i - 1, j }); queue.add(new int[] { i, j + 1 }); queue.add(new int[] { i, j - 1 }); } } } }