小岛问题
LeetCode 上有很多小岛题,虽然官方没有这个标签, 但是在我这里都差不多。不管是思路还是套路都比较类似,大家可以结合起来练习。
不严谨地讲,小岛问题是 DFS 的子专题。

套路

这种题目的套路都是 DFS,从一个或多个入口 DFS 即可。 DFS 的时候,我们往四个方向延伸即可。
一个最经典的代码模板:
1
seen = set()
2
def dfs(i, j):
3
if i 越界 or j 越界: return
4
if (i, j) in seen: return
5
temp = board[i][j]
6
# 标记为访问过
7
seen.add((i, j))
8
# 上
9
dfs(i + 1, j)
10
# 下
11
dfs(i - 1, j)
12
# 右
13
dfs(i, j + 1)
14
# 左
15
dfs(i, j - 1)
16
# 撤销标记
17
seen.remove((i, j))
18
# 单点搜索
19
dfs(0, 0)
20
# 多点搜索
21
for i in range(M):
22
for j in range(N):
23
dfs(i, j)
Copied!
有时候我们甚至可以不用 visited 来标记每个 cell 的访问情况, 而是直接原地标记,这种算法的空间复杂度会更好。这也是一个很常用的技巧, 大家要熟练掌握。
1
def dfs(i, j):
2
if i 越界 or j 越界: return
3
if board[i][j] == -1: return
4
temp = board[i][j]
5
# 标记为访问过
6
board[i][j] = -1
7
# 上
8
dfs(i + 1, j)
9
# 下
10
dfs(i - 1, j)
11
# 右
12
dfs(i, j + 1)
13
# 左
14
dfs(i, j - 1)
15
# 撤销标记
16
board[i][j] = temp
17
# 单点搜索
18
dfs(0, 0)
19
# 多点搜索
20
for i in range(M):
21
for j in range(N):
22
dfs(i, j)
Copied!

相关题目

上面四道题都可以使用常规的 DFS 来做。 并且递归的方向都是上下左右四个方向。更有意思的是,都可以采用原地修改的方式,来减少开辟 visited 的空间。
其中 463 题, 只是在做 DFS 的时候,需要注意相邻的各自边长可能会被重复计算, 因此需要减去。这里我的思路是:
  • 遇到陆地就加 4
  • 继续判断其左侧和上方是否为陆地
    • 如果是的话,会出现重复计算,这个时候重复计算的是 2,因此减去 2 即可
    • 如果不是,则不会重复计算, 不予理会即可
注意,右侧和下方的就不需要算了,否则还是会重复计算。
代码:
1
class Solution:
2
def islandPerimeter(self, grid: List[List[int]]) -> int:
3
def dfs(i, j):
4
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
5
return 0
6
grid[i][j] = -1
7
ans = 4 + dfs(i + 1, j) + dfs(i - 1, j) + \
8
dfs(i, j + 1) + dfs(i, j - 1)
9
if i > 0 and grid[i - 1][j] != 0:
10
ans -= 2
11
if j > 0 and grid[i][j - 1] != 0:
12
ans -= 2
13
return ans
14
15
m, n = len(grid), len(grid[0])
16
for i in range(m):
17
for j in range(n):
18
if grid[i][j] == 1:
19
return dfs(i, j)
Copied!
当然, 你选择判断右侧和下方也是一样的,只需要改两行代码即可,这两种算法没有什么区别。代码:
1
class Solution:
2
def islandPerimeter(self, grid: List[List[int]]) -> int:
3
def dfs(i, j):
4
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
5
return 0
6
grid[i][j] = -1
7
ans = 4 + dfs(i + 1, j) + dfs(i - 1, j) + \
8
dfs(i, j + 1) + dfs(i, j - 1)
9
# 这里需要变
10
if i < m - 1 and grid[i + 1][j] != 0:
11
ans -= 2
12
# 这里需要变
13
if j < n - 1 and grid[i][j + 1] != 0:
14
ans -= 2
15
return ans
16
17
m, n = len(grid), len(grid[0])
18
for i in range(m):
19
for j in range(n):
20
if grid[i][j] == 1:
21
return dfs(i, j)
Copied!
如果你下次碰到了小岛题目, 或者可以抽象为小岛类模型的题目,可以尝试使用本节给大家介绍的模板。这种题目的规律性很强, 类似的还有石子游戏,石子游戏大多数可以使用 DP 来做,这就是一种套路。

扩展

实际上,很多题都有小岛题的影子,所谓的小岛题的核心是求连通区域。如果你能将问题转化为求连通区域,那么就可以使用本节的思路去做。 比如 959. 由斜杠划分区域
题目描述:
1
在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
2
3
(请注意,反斜杠字符是转义的,因此 \ 用 "\\" 表示。)。
4
5
返回区域的数目。
6
7
示例 1:
8
9
输入:
10
[
11
" /",
12
"/ "
13
]
14
输出:2
15
解释:2x2 网格如下:
Copied!
1
示例 2:
2
3
输入:
4
[
5
" /",
6
" "
7
]
8
输出:1
9
解释:2x2 网格如下:
Copied!
1
示例 3:
2
3
输入:
4
[
5
"\\/",
6
"/\\"
7
]
8
输出:4
9
解释:(回想一下,因为 \ 字符是转义的,所以 "\\/" 表示 \/,而 "/\\" 表示 /\。)
10
2x2 网格如下:
Copied!
1
示例 4:
2
3
输入:
4
[
5
"/\\",
6
"\\/"
7
]
8
输出:5
9
解释:(回想一下,因为 \ 字符是转义的,所以 "/\\" 表示 /\,而 "\\/" 表示 \/。)
10
2x2 网格如下:
Copied!
1
示例 5:
2
3
输入:
4
[
5
"//",
6
"/ "
7
]
8
输出:3
9
解释:2x2 网格如下:
Copied!
1
提示:
2
3
1 <= grid.length == grid[0].length <= 30
4
grid[i][j] 是 '/'、'\'、或 ' '。
Copied!
实际上,如果你将题目中的 "/" 和 "\" 都转化为 一个 3 x 3 的网格之后,问题就变成了求连通区域的个数,就可以用本节的思路去解决了。具体留给读者去思考吧,这里给大家贴一个 Python3 的代码。
1
class Solution:
2
def regionsBySlashes(self, grid: List[str]) -> int:
3
m, n = len(grid), len(grid[0])
4
new_grid = [[0 for _ in range(3 * n)] for _ in range(3 * m)]
5
ans = 0
6
# 预处理,生成新的 3 * m * 3 * n 的网格
7
for i in range(m):
8
for j in range(n):
9
if grid[i][j] == '/':
10
new_grid[3 * i][3 * j + 2] = 1
11
new_grid[3 * i + 1][3 * j + 1] = 1
12
new_grid[3 * i + 2][3 * j] = 1
13
if grid[i][j] == '\\':
14
new_grid[3 * i][3 * j] = 1
15
new_grid[3 * i + 1][3 * j + 1] = 1
16
new_grid[3 * i + 2][3 * j + 2] = 1·
17
def dfs(i, j):
18
if 0 <= i < 3 * m and 0 <= j < 3 * n and new_grid[i][j] == 0:
19
new_grid[i][j] = 1
20
dfs(i + 1, j)
21
dfs(i - 1, j)
22
dfs(i, j + 1)
23
dfs(i, j - 1)
24
for i in range(3 * m):
25
for j in range(3 * n):
26
if new_grid[i][j] == 0:
27
ans += 1
28
dfs(i, j)
29
return ans
Copied!
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
复制链接