代码收藏家 笔记：蓝桥python搜索（3-1）——DFS基础和DFS回溯
搜索算法：穷举问题解空间部分/所有情况，从而求出问题的解
深度优先搜索：
本质上是暴力枚举
深度优先：尽可能一条路走到底，走不了再回退
目录
二、DFS和n重循环
三、例题分析
例题 P4124 分糖果
例题 P3505 买瓜
四、回溯法
五、回溯模板
六、例题分析
例题 P1508 N皇后
例题 P182 小朋友崇拜圈
例题 P178 全球变暖
输入描述
二、DFS和n重循环
给定一个数字x，将其拆分成3个正整数，后一个要求大于等于前一个，给出方案。
最简单的思想：三重循环暴力求解
如果是拆分成n个正整数？
就需要实现n重循环
n重循环=特定的树状结构=DFS搜索
给定一个数字x，将其拆分成n个正整数，后一个要求大于等于前一个，给出方案。
n重循环：n层的树 DFS：从上往下找一条合法的路径（路径值不递减、长度为n，和为x）
def dfs(depth): """ :param depth: 当前为第几重循环 :return: """ global cnt cnt = cnt + 1 #第0重 - 第n-1重都已经选好数字, 此时只需要判断答案 if depth == n: #条件一: 数字需要递增 for i in range(1, n): if a[i] >= a[i - 1]: continue else: return #条件二: 数字和为x if sum(a)!= x: return #此时是答案 print(a) return #第depth层进行选择数字:[1,x]进行枚举 for i in range(1, x + 1): #选择第depth层的数字 a[depth] = i #递归进入下一层 dfs(depth + 1) x, n = map(int, input().split()) #记录每层选择数字 a = [0] * n #计算次数: cnt cnt = 0 dfs(0) print("累计计算次数={}".format(cnt))
把条件放在枚举的时候判断可以降低计算量：剪枝 def dfs(depth,last_val): """ :param depth:当前第几重循环 :param last_val: 从上一层的开始枚举而不是从 1 开始（递增） :return: """ global cnt cnt=cnt+1 # 第0重-第n-重都已经选好了数字，此时只需要判断答案 if depth==n: # 条件二：数字和为x if sum(a)!=x: return print(a) return #第depth层进行选择数字：[1,x]进行枚举 for i in range(last_val,x+1): a[depth]=i dfs(depth+1,i) x, n = map(int, input().split()) #记录每层选择数字 a = [0] * n #计算次数: cnt cnt = 0 dfs(0,1) # 只枚举正整数 print("累计计算次数={}".format(cnt))
模板
def dfs(depth): """ :param depth: 当前为第几重循环 :return: """ if depth == N: #N重循环最内层执行的代码 return #每重循环进行的枚举选择
三、例题分析
例题 P4124 分糖果
两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。糖果必须全部分完。
只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
7重循环，每重循环表示1个小朋友 每个小朋友枚举所有的糖果情况
ans = 0 def dfs(depth, n, m): """ :param depth: 第depth个小朋友 :param n: 第一类糖果数量 :param m: 第二类糖果数量 :return: """ if depth == 7: # 分完后没有糖果 if n == 0 and m == 0: global ans ans += 1 return # 每个小朋友的情况 # 枚举第一种糖果 for i in range(0, 6): # 枚举第二种糖果 for j in range(0, 6): # 第depth个小朋友有第i个第一种，j个第二种 if 2 <= i + j <= 5 and i <= n and j <= m: dfs(depth + 1, n - i, m - j) dfs(0, 9, 16) print(ans)
例题 P3505 买瓜
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 Ai。
小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1。
输入格式
输入的第一行包含两个整数 n，m，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。
输出格式
输出一行包含一个整数表示答案。
N重循环，每重循环三种情况：
买1个 买一半 不买 def dfs(depth, s, cnt): """ :param depth: 第depth层循环 :param s: 当前累计的重量 :param cnt: 当前的劈的西瓜个数 :return: """ # 递归出口 # 1、当前累计重量已经超过m, 不需要继续下去 if s > m: return # 2、当前累计重量等于m, 直接更新答案 if s == m: global ans ans = min(ans, cnt) # 3、第depth层时, 停止继续递归 if depth == n: return # 买一个 dfs(depth + 1, s + w[depth], cnt) # 买半个 dfs(depth + 1, s + w[depth] // 2, cnt + 1) # 不买 dfs(depth + 1, s, cnt) n, m = map(int, input().split()) m *= 2 # 避免小数 w = list(map(int, input().split())) w = [x * 2 for x in w] ans = n + 1 dfs(0, 0, 0) if ans == n + 1: ans = -1 print(ans)目前的算法能通过65%
四、回溯法
回溯：就是DFS的一种，在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯更强调：此路不通，另寻他路，走过的路需要打标记
回溯法一般在DFS的基础上加上一些剪枝策略
五、回溯模板
排列要求数字不重复——每次选择的数字需要打标记——vis数组 要输出当前排列——记录路径——path数组 回溯：先打标记、记录路径、然后下一层、回到上一层、清除标记 def dfs(depth): #depth:第depth个数字 if depth == n: print(path) return for i in range(1,n+1): #选择的数字必须未标记 if vis[i]: continue #第depth个数字选择i vis[i]=True path.append(i) dfs(depth+1) # 回溯操作，处理下一个数字，当前数字i标记为待使用 vis[i]=False path.pop(-1) n=int(input()) vis=[False]*(n+1) path=[] dfs(0)def dfs(depth): #当前为第depth个数字, 0到depth - 1已经设置好 if depth == n: print(path) return #枚举第depth个数字 for i in range(1, n + 1): #数字i必须先前未选择 if vis[i] is False: #标记当前状态 vis[i] = True #记录当前路径 path.append(i) #进行下一层搜索 dfs(depth + 1) #回溯，清空标记 vis[i] = False path.pop(-1) n = int(input()) path = [] vis = [False] * (n + 1) dfs(0)
给定N个数字，求子集
def dfs(depth): #depth:第depth个数字 if depth == n: print(path) return # 选 path.append(a[depth]) dfs(depth + 1) path.pop(-1) # 不选 dfs(depth + 1) n=int(input()) a = list(map(int, input().split())) # vis=[False]*(n+1) path=[] dfs(0)
六、例题分析
例题 P1508 N皇后
在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45° 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。
输入描述
输入中有一个正整数 N≤10，表示棋盘和皇后的数量
输出描述
为一个正整数，表示对应输入行的皇后的不同放置数量。
dfs枚举每一行放置的列 标记：
每列只能放一个
主对角线：x + y
副对角线：x – y + n
def dfs(x): if x==n+1: global ans ans=ans+1 return for y in range(1,n+1): #列、主对角线、副对角线不能被攻击到 if vis1[y] or vis2[x+y] or vis3[x-y+n]: continue #(x,y)合法 #打标记，进入下一层搜索，回到该层，清空标记 # 标记当前状态 vis1[y] = vis2[x+y] = vis3[x-y+n] = True dfs(x + 1) # 清除标记 vis1[y] = vis2[x+y] = vis3[x-y+n] = False n = int(input()) ans = 0 # 分别表示列、主对角线、副对角线是否被标记 vis1 = [False] * (n + 1) vis2 = [False] * (2 * n + 1) vis3 = [False] * (2 * n + 1) # 如果下标设置从一开始 dfs(1) print(ans)def dfs(depth): # 当前为第depth行数字, 0到depth - 1行已经设置好 if depth == n: global ans ans = ans + 1 return # 枚举第depth行放在哪列 for i in range(1, n + 1): # 坐标为: (depth, i) # 第i列先前未选择、主对角线未选择、副对角线未选择 if vis1[i] is False and vis2[depth + i] is False and vis3[depth - i + n] is False: # 标记当前状态 vis1[i] = True vis2[depth + i] = True vis3[depth - i + n] = True dfs(depth + 1) # 清除标记 vis1[i] = False vis2[depth + i] = False vis3[depth - i + n] = False n = int(input()) ans = 0 vis1 = [False] * (n + 1) vis2 = [False] * (2 * n + 1) vis3 = [False] * (2 * n + 1) dfs(0) print(ans)
例题 P182 小朋友崇拜圈
班里 N 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？
小朋友编号为 1,2,3,⋯N。
输入描述
输入第一行，一个整数 N（3<N<10^5）。
接下来一行 N 个整数，由空格分开。
输出描述
要求输出一个整数，表示满足条件的最大圈的人数。
dfs(x, length)：走到 x，已经走了 length 步
import sys #扩栈：递归层数过大，需要设置最大栈空间 sys.setrecursionlimit(100000) #当前位于x，步长为length def dfs(x, length): #记录当前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 = list(map(int, input().split())) a = [0] + a vis = [0] * (n + 1) ans = 0 for i in range(1, n + 1): # 对于每个单独的圈都要做一次dfs if vis[i] == 0: dfs(i, 1) print(ans)import sys sys.setrecursionlimit(100000) def dfs(x, length): # print(x, length) # 记录当前x，已经走了length步 vis[x] = length # 如果下一步已经走过，则说明当前已经进入了一个圈 if vis[a[x]]: # 更新最大圈 global ans ans = max(ans, length - vis[a[x]] + 1) # 下一步没走过，走下一步 else: dfs(a[x], length + 1) n = int(input()) a = list(map(int, input().split())) a = [0] + a vis = [0] * (n + 1) ans = 0 for i in range(1, n + 1): if vis[i] == 0: dfs(i, 1) print(ans)
例题 P178 全球变暖
你有一张某海域 NxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：
…….
.##….
.##….
….##.
..####.
…###.
…….
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…….
…….
…….
…….
….#..
…….
…….
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 N (1≤N≤1000)N。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、
输出一个整数表示答案。
1、求解当前有多少个岛屿
2、如果当前岛屿中不存在“高地”，则该岛屿会被淹没
import sys sys.setrecursionlimit(1000000) # 方向数组，用于表示上下左右四个方向 dir = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 深度优先搜索函数 def dfs(x, y, N, Map, vis, flag): # 标记当前点 vis[x][y] = 1 # 判断当前点是否为高地 is_high_ground = True for dx, dy in dir: new_x, new_y = x + dx, y + dy # 检查边界和是否为陆地 if 0 <= new_x < N and 0 <= new_y < N and Map[new_x][new_y]!= '#': is_high_ground = False break if is_high_ground: flag = 1 # 把四周的未遍历的土地继续遍历 for i in range(4): xx, yy = x + dir[i][0], y + dir[i][1] # 检查边界、是否为陆地以及是否未访问 if 0 <= xx < N and 0 <= yy < N and Map[xx][yy] == '#' and vis[xx][yy] == 0: flag = dfs(xx, yy, N, Map, vis, flag) return flag N = int(input()) Map = [] vis = [] for i in range(N): Map.append(list(input())) vis.append([0] * N) ans = 0 for i in range(N): for j in range(N): if Map[i][j] == '#' and vis[i][j] == 0: flag = 0 flag = dfs(i, j, N, Map, vis, flag) if flag == 0: ans += 1 print(ans)
作者：寒舍书生
