# 「力扣」第 200 题：岛屿数量（中等）
# 题目描述
给你一个由 '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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
# 方法：广度优先遍历
在写「广度优先遍历」的时候，要注意一点：
所有加入队列的结点，都应该马上被标记为「已经访问」，否则有可能会被重复加入队列。
我一开始在编写的时候，等到队列出队的时候才标记「已经访问」，事实上，这种做法是错误的。因为如果不在刚刚入队列的时候标记「已经访问」，相同的结点很可能会重复入队，如果你遇到「超时」的提示，你不妨把你的队列打印出来看一下，就很清楚看到我说的这一点。
参考代码：
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<Integer> 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)
作者：liweiwei1419 链接：https://suanfa8.com/breadth-first-search/solutions-1/0200-number-of-islands 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。