【废物研究生零基础刷算法】DFS与递归（二）习题

P2089烤鸡（指数）

说明：对于100%的数据，n小于等于5000

N = 30
n = int(input())
arr = [0] * N  # 存储当前方案，索引 1 到 10
res = 0
memo = []  # 存储所有方案的列表

def dfs(x, sum_val):  # x 表示当前配料，sum_val 表示当前总和
    global res
    if sum_val > n:  # 超过 n，剪枝
        return
    
    if x > 10:  # 填满 10 种配料
        if sum_val == n:  # 总和恰好为 n
            res += 1
            scheme = [arr[i] for i in range(1, 11)]  # 复制当前方案
            memo.append(scheme)
        return
    
    for i in range(1, 4):  # 每种配料选 1 到 3
        arr[x] = i
        dfs(x + 1, sum_val + i)  # 累加 i 到 sum_val

dfs(1, 0)  # 从第 1 种配料开始，总和为 0

print(res)  # 输出方案总数
if res > 0:
    for scheme in memo:  # 输出每种方案
        print(" ".join(map(str, scheme)))

P1088火星人（全排列）

import sys
sys.setrecursionlimit(10**9)
n = int(input())
m = int(input())
mars = [0] + list(map(int, input().split()))
ans = [0 for _ in range(n+1)]
st = [0 for _ in range(n+1)]
cnt = 0
# 通常会用深度优先搜索（DFS）生成所有可能的排列，并通过一个计数器 cnt 来跟踪当前是第几个排列。cnt 的具体作用是：
# 每当 DFS 生成一个完整的排列时，cnt 增加 1。
# 通过 cnt，我们可以知道当前排列在字典序中的位置（第几个）

def dfs(x):
    global cnt
    if x > n:
        cnt += 1
        if cnt == m + 1:  # 说明我们已经生成了从火星人排列开始的第 M 个后续排列（包括火星人排列本身后的第 M 个
            print(*ans[1:])
            exit()
        return
    i = 1
    while i <= n:
        if cnt == 0:
            i = mars[x]
        if not st[i]:
            st[i] = 1
            ans[x] = i
            dfs(x + 1)
            st[i] = 0
            ans[x] = 0
        i += 1

dfs(1)

P1149火柴棒等式（指数+预处理）

N = 1010
n = int(input())
n -= 4
huo_1000 = [0] * N
huo = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
nums = huo + huo_1000
arr = [0] * N  # 存放当前状态
count = 0


def col(x):
    if nums[x] > 0:
        return nums[x]
    else:
        sumFire = 0
        while x:
            sumFire += nums[int(x % 10)]
            x /= 10
        return sumFire


def dfs(x, sum):
    global count
    if sum > n:
        return
    if x > 3:
        if arr[1] + arr[2] == arr[3] and sum == n:
            count += 1
            print(*arr[0:4])
        return

    for i in range(0, 1000):  # 每个位置遍历火柴的数量
        arr[x] = i
        dfs(x + 1, sum + col(i))
        arr[x] = 0


dfs(1, 0)
print(count)
# 程序从 dfs(1, 0) 开始递归搜索，这意味着它首先尝试确定A的值，然后是B，最后是C。如果从arr[0]开始，则可能意味着不同的设计选择，但基于上述逻辑，这里的实现直接跳过了arr[0]，从arr[1]开始代表A。

P2036 PERKET（指数）

# 最大配料数量
N = 50
# 读取配料数量
n = int(input())
# 用于标记每种配料的选择状态，0 未考虑，1 选择，2 不选择
st = [0] * (N + 1)
# arr是记录当前状态，如果没有输出的话不需要
# 初始化最小差值为一个较大的值
res = float('inf')
# 存储每种配料的酸度
acid = [0]
# 存储每种配料的苦度
bitter = [0]

# 读取每种配料的酸度和苦度
for i in range(n):
    line = list(map(int, input().split()))
    acid.append(line[0])
    bitter.append(line[1])

def dfs(x):
    global res
    # 当考虑完所有配料时
    if x > n:
        # 标记是否选择了至少一种配料
        has_ingredient = False
        acid_sum = 1
        bitter_sum = 0
        # 遍历所有配料
        for i in range(1, n + 1):
            if st[i] == 1:
                has_ingredient = True
                acid_sum *= acid[i]
                bitter_sum += bitter[i]
        # 只有选择了至少一种配料时才更新结果
        if has_ingredient:
            res = min(res, abs(acid_sum - bitter_sum))
        return
    # 选择当前配料
    st[x] = 1
    dfs(x + 1)
    # 不选择当前配料
    st[x] = 2
    dfs(x + 1)
    # 恢复状态
    st[x] = 0

# 从索引 1 开始进行深度优先搜索
dfs(1)
print(res)

棋盘问题（全排列）

def dfs(x, count, n, k, g, st):
    global res
    if count == k:  # 已经放置了 k 个棋子
        res += 1
        return
    if x >= n:  # 超出棋盘行数（从 0 到 n-1）
        return

    # 尝试在当前行 x 放置棋子
    for i in range(n):
        if not st[i] and g[x][i] == '#':  # 列未使用且当前位置是棋盘区域
            st[i] = True
            dfs(x + 1, count + 1, n, k, g, st)
            st[i] = False

    # 也可以选择当前行不放棋子，直接跳到下一行
    dfs(x + 1, count, n, k, g, st)

# 主程序
while True:
    line1 = list(map(int, input().split()))
    n = line1[0]
    k = line1[1]
    if n == -1 and k == -1:
        break

    # 初始化
    g = []  # 棋盘
    res = 0  # 结果
    st = [False] * n  # 标记每列是否使用

    # 读取棋盘
    for _ in range(n):
        g.append(list(input()))

    dfs(0, 0, n, k, g, st)
    print(res)

数的划分（组合）

line1 = list(map(int, input().split()))
n = line1[0]
k = line1[1]
arr = [0] * n
res = 0


def dfs(x, start, num_sum):
    global res
    if num_sum > n:
        return

    if x == k:
        if num_sum == n:
            res += 1
        return

    for i in range(start, n):  # 题目要求每份不能为空，即最小值为1,而且为了保证是递增序列要从start开始
        arr[i] = i
        dfs(x + 1, i, num_sum + i)
        arr[i] = i


dfs(0, 1, 0)
print(res)

【迷宫问题】

习题

N = 20
line1 = list(map(int, input().split()))
w = line1[0]
h = line1[1]
g = []
for i in range(h):
    line = list(input())
    g.append(line)
#
# for row in g:
#     print(row)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
st = [[False for _ in range(N)] for _ in range(N)]
res = 0


def dfs(x, y):
    global res
    for i in range(4):
        a = x + dx[i]
        b = y + dy[i]

        if a < 0 or a >= h or b < 0 or b >= w: continue
        if g[a][b] == '#': continue
        if st[a][b]: continue

        st[a][b] = True
        res += 1
        dfs(a, b)


for i in range(h):
    for j in range(w):
        if g[i][j] == '@':
            dfs(i, j)

# res+=1
print(res)

【最大连通块问题】P1596 [USACO10OCT] Lake Counting S

line1 = list(map(int, input().split()))
n = line1[0]
m = line1[1]
st = [[False for _ in range(m)] for _ in range(n)]  # 存放状态，被选择过or没被选择过
g = []
for row in range(n):
    line = list(input())
    g.append(line)

res = 0

# for row in g:
#     print(row)

dx = [1, 1, 1, 0, 0, -1, -1, -1]
dy = [-1, 0, 1, 1, -1, 1, 0, -1]  # 最好配对记住


def dfs(x, y):
    for i in range(8):
        a = x + dx[i]
        b = y + dy[i]

        if a < 0 or b < 0 or a >= n or b >= m: continue
        if g[a][b] == '.': continue
        if st[a][b]: continue

        st[a][b] = True
        dfs(a, b)


for i in range(n):
    for j in range(m):
        if g[i][j] == 'W' and st[i][j] == False:
            dfs(i, j)
            res += 1
print(res)