给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
方法一：深度优先搜索 【通过】
直觉
将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边。
算法
线性扫描整个二维网格，如果一个结点包含 1，则以其为根结点启动深度优先搜索。在深度优先搜索过程中，每个访问过的结点被标记为 0。计数启动深度优先搜索的根结点的数量，即为岛屿的数量。
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}方法二：广度优先遍历
除了 “深度优先遍历”，你还可以使用 “广度优先遍历”，此时你就不用回溯了。“广度优先遍历” 需要一个 “辅助队列”。
深度优先使用递归，一个方向走到底，广度优先使用一个辅助队列，先处理一个点的所有直接相邻节点
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
Queue<Integer> nei***ors = new LinkedList<>();
nei***ors.add(r * nc + c);
while (!nei***ors.isEmpty()) {
int id = nei***ors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
nei***ors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
nei***ors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
nei***ors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
nei***ors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/