「力扣」第 200 题：岛屿数量
题解地址：DFS + BFS + 并查集（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：200. 岛屿数量。
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000输出: 1
示例 2:输入:
11000
11000
00100
00011输出: 3
方法：广度优先遍历
在写「广度优先遍历」的时候，要注意一点：
所有加入队列的结点，都应该马上被标记为「已经访问」，否则有可能会被重复加入队列。
我一开始在编写的时候，等到队列出队的时候才标记「已经访问」，事实上，这种做法是错误的。因为如果不在刚刚入队列的时候标记「已经访问」，相同的结点很可能会重复入队，如果你遇到「超时」的提示，你不妨把你的队列打印出来看一下，就很清楚看到我说的这一点。
参考代码：
Java 代码：
import java.util.LinkedList;
/**
* 方法二：广度优先遍历
*/
public class Solution2 {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
rows = grid.length;
if (rows == 0) {
return 0;
}
cols = grid[0].length;
boolean[][] marked = new boolean[rows][cols];
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 如果是岛屿中的一个点，并且没有被访问过
// 从坐标为 (i,j) 的点开始进行广度优先遍历
if (!marked[i][j] && grid[i][j] == '1') {
count++;
LinkedList queue = new LinkedList<>();
// 小技巧：把坐标转换为一个数字
// 否则，得用一个数组存，在 Python 中，可以使用 tuple 存
queue.addLast(i * cols + j);
// 注意：这里要标记上已经访问过
marked[i][j] = true;
while (!queue.isEmpty()) {
int cur = queue.removeFirst();
int curX = cur / cols;
int curY = cur % cols;
// 得到 4 个方向的坐标
for (int k = 0; k < 4; k++) {
int newX = curX + directions[k][0];
int newY = curY + directions[k][1];
// 如果不越界、没有被访问过、并且还要是陆地，我就继续放入队列，放入队列的同时，要记得标记已经访问过
if (inArea(newX, newY) && grid[newX][newY] == '1' && !marked[newX][newY]) {
queue.addLast(newX * cols + newY);
// 【特别注意】在放入队列以后，要马上标记成已经访问过，语义也是十分清楚的：反正只要进入了队列，你迟早都会遍历到它
// 而不是在出队列的时候再标记
// 【特别注意】如果是出队列的时候再标记，会造成很多重复的结点进入队列，造成重复的操作，这句话如果你没有写对地方，代码会严重超时的
marked[newX][newY] = true;
}
}
}
}
}
}
return count;
}
private boolean inArea(int x, int y) {
// 等于号这些细节不要忘了
return x >= 0 && x < rows && y >= 0 && y < cols;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
char[][] grid1 = {
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'}};
int numIslands1 = solution2.numIslands(grid1);
System.out.println(numIslands1);
char[][] grid2 = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
int numIslands2 = solution2.numIslands(grid2);
System.out.println(numIslands2);
}
} Python 代码：
from typing import List
from collections import deque
class Solution:
# x-1,y
# x,y-1 x,y x,y+1
# x+1,y
# 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
# 特判
if m == 0:
return 0
n = len(grid[0])
marked = [[False for _ in range(n)] for _ in range(m)]
count = 0
# 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作
for i in range(m):
for j in range(n):
# 只要是陆地，且没有被访问过的，就可以使用 BFS 发现与之相连的陆地，并进行标记
if not marked[i][j] and grid[i][j] == '1':
# count 可以理解为连通分量，你可以在广度优先遍历完成以后，再计数，
# 即这行代码放在【位置 1】也是可以的
count += 1
queue = deque()
queue.append((i, j))
# 注意：这里要标记上已经访问过
marked[i][j] = True
while queue:
cur_x, cur_y = queue.popleft()
# 得到 4 个方向的坐标
for direction in self.directions:
new_i = cur_x + direction[0]
new_j = cur_y + direction[1]
# 如果不越界、没有被访问过、并且还要是陆地，我就继续放入队列，放入队列的同时，要记得标记已经访问过
if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
queue.append((new_i, new_j))
#【特别注意】在放入队列以后，要马上标记成已经访问过，语义也是十分清楚的：反正只要进入了队列，你迟早都会遍历到它
# 而不是在出队列的时候再标记
#【特别注意】如果是出队列的时候再标记，会造成很多重复的结点进入队列，造成重复的操作，这句话如果你没有写对地方，代码会严重超时的
marked[new_i][new_j] = True
#【位置 1】
return count
if __name__ == '__main__':
grid = [['1', '1', '1', '1', '0'],
['1', '1', '0', '1', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '0', '0', '0']]
# grid = [["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "0", "1", "1"],
# ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "0"],
# ["1", "0", "1", "1", "1", "0", "0", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "0", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1"],
# ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "0", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1"],
# ["1", "0", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "0"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "0"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
# ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]]
solution = Solution()
result = solution.numIslands(grid)
print(result)（本节完）
