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

文章目录 P2089烤鸡（指数）P1088火星人（全排列）P1149火柴棒等式（指数+预处理）P2036 PERKET（指数）棋盘问题（全排列）数的划分（组合）【迷宫问题】【最大连通块问题】P1596 [USACO10OCT] Lake Counting S

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)