岛屿数量：中等
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 |
1 |
2 |
输入 |
grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] |
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] |
输出 |
1 |
3 |
总体思路
看示例 2：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
假设你是哥伦布。先从左上角开始，把第一个岛全部插上旗子🚩，这里用 2 表示。插满旗子后，把答案（岛屿个数）加一。
⚠注意：在岛上，你只能上下左右走，不能斜方向走。
2 2 0 0 0
2 2 0 0 0
0 0 1 0 0
0 0 0 1 1
继续遍历，寻找其他的岛屿，也就是 1。找到 1 意味着发现了一个新的岛，继续插上旗子🚩，把答案加一。
2 2 0 0 0
2 2 0 0 0
0 0 2 0 0
0 0 0 1 1
继续遍历，寻找其他的岛屿。找到 1 意味着发现了一个新的岛，插满旗子🚩，把答案加一。
2 2 0 0 0
2 2 0 0 0
0 0 2 0 0
0 0 0 2 2
如果没有 1 了，算法就结束了，返回答案。
细节
一旦我们发现 (i,j) 是 1，就从 (i,j) 开始，DFS 这个岛。
每一步可以往左右上下四个方向走，也就是
(i,j−1),(i,j+1),(i−1,j),(i+1,j)
这四个格子。
每次到达一个新的格子，就插上旗子🚩，把 grid[i][j] 改成 2。
如果 (i,j) 出界，或者 (i,j) 是水，或者 (i,j) 已经插上了旗子🚩，就不再继续往下递归。
⚠注意：DFS 的过程中，最重要的是不能重复访问之前访问过的格子。
比如从左上角 (0,0) 向右移动到 (0,1)，然后从 (0,1) 又向左移动到 (0,0)，再从 (0,0) 向右移动到 (0,1)，如此往复，就无限递归下去了。
怎么避免重复访问？本题的做法是把访问过的格子都插上旗子🚩。例如从 (0,1) 往左走，发现 (0,0) 是插过旗子的格子，就不继续走了。
可以把访问过的 grid[i][j] 改成 0 吗？可以。相当于把访问过的岛摧毁掉。其实，改成除了 1 以外的任何值都行。
我可以把 grid[i][j] = '2' 写在 dfs 的最后一行吗？不行。如果这样写，我们会先往下递归，比如从左上角 (0,0) 向右移动到 (0,1)，然后从 (0,1) 又向左移动到 (0,0)，会反复横跳，无限递归。
DFS 中能否只考虑往右走和往下走？不行，比如蚊香形的岛屿，你在探索的时候必须具备上下左右走的能力。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(i: int, j: int) -> None:
# 出界，或者不是 '1'，就不再往下递归
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '2' # 插旗！避免来回横跳无限递归
dfs(i, j - 1) # 往左走
dfs(i, j + 1) # 往右走
dfs(i - 1, j) # 往上走
dfs(i + 1, j) # 往下走
ans = 0
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == '1': # 找到了一个新的岛
dfs(i, j) # 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
ans += 1
return ans
时间复杂度 |
空间复杂度 |
O(mn) |
O(mn) |
其中 m 和 n 分别为 grid 的行数和列数 |
最坏情况下，递归需要 O(mn) 的栈空间 |
腐烂的橘子：中等
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。
如果不可能，返回 -1 。
示例 |
1 |
输入 |
grid = [[2,1,1],[1,1,0],[0,1,1]] |
输出 |
4 |
|
示例 |
2 |
3 |
输入 |
grid = [[2,1,1],[0,1,1],[1,0,1]] |
grid = [[0,2]] |
输出 |
-1 |
0 |
左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上 |
因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 |
看示例 1：
- 统计所有初始就腐烂的橘子的位置，加到列表 q 中，现在 q=[(0,0)]。
- 初始化答案 ans=0。模拟橘子腐烂的过程，不断循环，直到没有新鲜橘子，或者 q 为空。
- 答案加一，在第 ans=1 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(0,1),(1,0)]。
- 答案加一，在第 ans=2 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(0,2),(1,1)]。
- 答案加一，在第 ans=3 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(2,1)]。
- 答案加一，在第 ans=4 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(2,2)]。
- 由于没有新鲜橘子，退出循环。
为了判断是否有永远不会腐烂的橘子（如示例 2），我们可以统计初始新鲜橘子的个数 fresh。在 BFS 中，每有一个新鲜橘子被腐烂，就把 fresh 减一，这样最后如果发现 fresh>0，就意味着有橘子永远不会腐烂，返回 −1。
代码实现时，在 BFS 中要将 grid[i][j]=1 的橘子修改成 2（或者其它不等于 1 的数），这可以保证每个橘子加入 q 中至多一次。如果不修改，我们就无法知道哪些橘子被腐烂过了，比如示例 1 中 (0,1) 去腐烂 (1,1)，而 (1,1) 在此之后又重新腐烂 (0,1)，如此反复，程序就会陷入死循环。读者可以注释掉下面代码中的 grid[i][j] = 2 这行代码试试。
如果代码不在 while 中判断 fresh>0，会发生什么？会在腐烂完所有新鲜橘子后，多循环一次。这会导致 ans 比实际多 1。
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
fresh = 0
q = []
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
fresh += 1 # 统计新鲜橘子个数
elif x == 2:
q.append((i, j)) # 一开始就腐烂的橘子
ans = 0
while q and fresh:
ans += 1 # 经过一分钟
tmp = q
q = []
for x, y in tmp: # 已经腐烂的橘子
for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1): # 四方向
if 0 <= i < m and 0 <= j < n and grid[i][j] == 1: # 新鲜橘子
fresh -= 1
grid[i][j] = 2 # 变成腐烂橘子
q.append((i, j))
return -1 if fresh else ans