一、题目描述
给你一个由 '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'
二、思路讲解
2.1 方法一：深度优先遍历dfs
目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。那么我们可以利用深度优先搜索去寻找1，一次完整的遍历可以找到联通的一片岛屿。
递归终止条件：
- (i, j) 越过矩阵边界;
- grid[i][j] == 0，代表此分支已越过岛屿边界。
需要注意的是，在搜索岛屿的同时，执行 grid[i][j] = '0'，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。
我们在主循环中遍历整个矩阵，当遇到 grid[i][j] == '1' 时，从此点开始做深度优先搜索 dfs，并且岛屿数 count + 1 ，一次dfs即可清空一片岛屿。循环结束后返回count即为所求。
2.2 方法二：广度优先遍历bfs
思路与深搜的思路相同，只不过遍历寻找边界的方式略有不同。
三、Java代码实现
3.1 深度优先遍历dfs
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++) { //一块联通区域只会被统计一次，因为一次完整的递归会将联通区域中所有1抹去 if(grid[i][j] == '1') { dfs(grid, i, j); count++; } } } return count; } /** 深度优先搜索 */ void dfs(char [][]grid, int x, int y) { //到达网格边缘或水边，终止递归（剪枝） if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y]=='0') { return; } //将岛屿的1抹去，避免重复搜索 grid[x][y] = '0'; dfs(grid, x-1, y); dfs(grid, x+1, y); dfs(grid, x, y-1); dfs(grid, x, y+1); } }
3.2 广度优先遍历bfs
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++) { //一块联通区域只会被统计一次，因为一次完整的搜索会将联通区域中所有1抹去 if(grid[i][j] == '1') { bfs(grid, i, j); count++; } } } return count; } /** 广度优先搜索 */ void bfs(char [][]grid, int i, int j) { Queue<int []> queue = new LinkedList<>(); queue.add(new int []{i, j}); while(!queue.isEmpty()){ int []removeArray = queue.poll(); int x = removeArray[0]; int y = removeArray[1]; if(x>=0 && y>=0 && x<grid.length && y<grid[0].length && grid[x][y]=='1') { //将岛屿上的1抹去，避免重复计算 grid[x][y] = '0'; queue.add(new int []{x-1, y}); queue.add(new int []{x+1, y}); queue.add(new int []{x, y-1}); queue.add(new int []{x, y+1}); } } } }
