DFS回溯

回溯法求排列数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def dfs(depth):
    # depth: 当前深度
    if depth == n:
        # 到达叶子节点，输出路径
        print(path)
        return
    
    # 选择范围
    for i in range(1, n+1):
        # 已经访问过的节点，跳过

        if vis[i]:
            continue

        # 符合条件的节点，加入路径
        vis[i] = True
        path.append(i)
        dfs(depth+1)
        # 回溯的时候，将当前节点从路径中移除
        vis[i] = False
        path.pop(-1)


n = int(input())
vis = [False] * (n+1)
path = []
dfs(0)

回溯法求子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
a = list(map(int, input().split()))

path = []
def dfs(depth):
    if depth == n:
        print(path)
        return
    
    # 选择当前节点
    path.append(a[depth])
    dfs(depth+1)
    path.pop(-1)

    # 不选择当前节点
    dfs(depth+1)

dfs(0)

1508N皇后问题

题目描述

在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def dfs (x):
    if x == n + 1:
        global ans
        ans += 1
        return 

    # 枚举每一列
    for y in range(1, n+1):
        # 当前坐标(x,y)
        if vis1[y] or vis2[x+y] or vis3[x-y+n]:
            continue
            
        # 标记当前坐标
        vis1[y] = True
        vis2[x+y] = True
        vis3[x-y+n] = True

        dfs(x+1)
        # 回溯
        vis1[y] = False
        vis2[x+y] = False
        vis3[x-y+n] = False


n = int(input())
vis1 = [False]*(n+1)
vis2 = [False]*(2*n+1)
vis3 = [False]*(2*n+1)

ans = 0
dfs(1)

print(ans)

小朋友崇拜圈

题目描述

班里 N 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。

在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。

求满足条件的圈最大多少人？

小朋友编号为 1,2,3,⋯N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 走到x位置，当前长度为length
import sys

sys.setrecursionlimit(1000000)

def dfs(x, length):
    vis[x] = length
    

    # 走到下一个点
    # 判断是否走过
    if vis[a[x]] != 0:
        global ans
        # 此时存在环
        ans = max(ans, length-vis[a[x]]+1)
    else:
        dfs(a[x], length+1)



n = int(input())
a = [0] + list(map(int, input().split()))

vis = [0] * (n+1)  # 表示步长

ans = 0

for i in range(1, n+1):
    if vis[i] == 0:
        dfs(i, 1)

print(ans)
  • 记得扩栈

全球变暖

题目描述

你有一张某海域 NxN 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

…….

.##….

.##….

….##.

..####.

…###.

…….

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

…….

…….

…….

…….

….#..

…….

…….

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys

sys.setrecursionlimit(1000000)  # 递归深度限制

def dfs(i, j):
    # 当前处于(i,j)位置，标记为已访问
    vis[i][j] = True
    # 四个方向进行DFS

    if map[i][j-1] == '#' and map[i][j+1] == '#' and map[i-1][j] == '#' and map[i+1][j] == '#':
        global flag
        flag = 1
    
    # 扩展，把相邻的点打上标记
    for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        x = i + dx
        y = j + dy
        if map[x][y] == '#' and not vis[x][y]:
            dfs(x, y)

n = int(input())

map = []

vis = []  # 记录是否访问过

for i in range(n):
    map.append(list(input()))
    vis.append([False] * n)

ans = 0
for i in range(n):
    for j in range(n):
        if map[i][j] == '#' and not vis[i][j]:

            flag = 0
            dfs(i, j)
            if flag == 0:
                ans += 1

print(ans)