-
DFS搜索和输出所有路径
2022.12将出版蓝桥杯大赛用书《蓝桥杯大赛-程序设计竞赛专题挑战教程》，作者：蓝桥杯组委会、罗勇军。
这本书解析了蓝桥杯大赛的常见考点，所有例题用C/C++、Python两种语言给出代码，适合C/C++组和Python组入门。
本文的内容摘抄自这本书。1、DFS搜所有路径
DFS是一种暴力搜索，它能搜所有可能的情况。
蓝桥杯大赛常常涉及到路径问题，需要用DFS寻找路径和输出路径，一般是输出一条符合要求的路径。
DFS的特点是“一路到底”，遇到终点时，就得到了从起点到终点的一条路径。所以搜所有路径用DFS写代码最方便。下面看DFS如何找到所有的路径。
图中，'@‘表示起点，’*‘表示终点，’.‘是可以走的点，’#'是墙壁不能走。
图(1)是搜到的第一条路径。从起点(1, 1)出发，查询它的“左-上-右-下”哪个方向能走，发现“左-上”不能走，可以走“右”。第一步走到右边的(2,1)。然后从(2, 1)继续走，它可以向上走到(2, 0)，但是后面就走不通了，退回来改走下面的(2, 2)。按这个方法，逐步深入走到终点，最后得到一条从起点(1, 1)到终点(0, 2)的路径“(1,1)->(2,1)->(2,2)->(1,2)->(0,2)”。后面C++代码中的a[nx][ny] = '#'的作用是“保存现场”。在这次DFS深入过程中，这条路径上曾经路过的点被“保存现场”，不允许再次经过。到达终点后，从终点退回，回溯寻找下一个路径。代码中的a[nx][ny] = '.'的作用是退回后“恢复现场”。
图(2)是搜到的第二条路径。在图(1)搜到一条路径后，从终点(0, 2)退回到(1, 2)，继续向下走到(1, 3)、(0, 3)、(0, 2)。
图(3)是搜到的第三条路径。从终点(0, 2)一路退回到(2, 2)后，才找到新路径。在退回的过程中，原来被“保存现场的”(0, 3)、(1, 3)、(0, 2)，重新被“恢复现场”，允许被经过。例如(1, 3)，在第二条路径中曾用过，这次再搜新路径时，在第三条路径中重新经过了它。如果不“恢复现场”，这个点就不能在新路径中重新用了。
总结“保存现场”和“恢复现场”的作用：
（1）“保存现场”的作用，是禁止重复使用。当搜索一条从起点到终点的路径时，这条路径上经过的点，不能重复经过，否则就兜圈子了，所以路径上的点需要“保存现场”，禁止再经过它。没有经过的点，或者碰壁后退回的点，都不能“保存现场”，这些点可能后面会进入这条路径。
（2）“恢复现场”的作用。当重新搜新的路径时，方法是从终点（或碰壁的点）沿着旧路径逐步退回，每退回一个点，就对这个点“恢复现场”，允许新路径重新经过这个点。例如图(2)和图(3)的点(1, 3)。2、用栈记录和输出路径
在DFS中，用栈来跟踪DFS的过程，记录走过的路径，是最方便的。DFS到某个格子时，把这个格子放到栈里，表示路径增加了这个格子。DFS回溯的时候，退出了这个格子，表示路径上不再包括这个格子，需要从栈中弹走这个格子。
3、例题
下面是本文自创的例题，演示上述的两个功能：
（1）用DFS搜索从起点到终点的所有路径；
（2）用栈记录路径。
例题：输出所有路径
【题目描述】给出一张格子图，输出从起点到终点的所有路径。
【输入描述】第一行是整数n，m，分别是行数和列数。后面n行，每行m个符号。只有两种符号：’•’能走，’#’是墙壁不能走。在每一步，都按左-上-右-下的顺序搜索。左上角是起点，坐标(0, 0)，右下角是终点，坐标(n-1, m-1)。
【输出描述】输出所有的路径。为了方便表示，约定每个小格子用一个数字代表，从西北角（左上角）开始编号: 0, 1, 2, 3…
【样例输入1】3 2 .. .. ..- 1
- 2
- 3
- 4
【样例输出1】
0 2 4 5 0 2 3 5 0 1 3 2 4 5 0 1 3 5- 1
- 2
- 3
- 4
【样例输入2】
3 4 .... ..#. ....- 1
- 2
- 3
- 4
【样例输出2】
0 4 8 9 5 1 2 3 7 11 0 4 8 9 10 11 0 4 5 1 2 3 7 11 0 4 5 9 10 11 0 1 5 4 8 9 10 11 0 1 5 9 10 11 0 1 2 3 7 11- 1
- 2
- 3
- 4
- 5
- 6
- 7
3.1 C++代码
下面代码中的函数dfs()搜索出所有代码，并打印出来。
vectorpath是一个栈，用于记录路径。在dfs()函数的开始，到达出口时，就根据path打印出路径。 #includeusing namespace std; int n,m; char a[25][25]; //存储格子图 vector<int> path; //path是一个栈，记录路径 int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; //4个方向：左、上、右、下 void dfs(int x,int y){ if(x==n-1 && y==m-1){ //终止条件：到达出口 for(int i = 0;i < path.size();i++) cout << path[i] <<" "; cout<<endl; return; } for(int i = 0;i < 4;i++){ int nx = x + dir[i][0],ny = y + dir[i][1]; if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny]=='.'){ a[nx][ny]='#'; path.push_back(nx*m + ny); //进栈，记录路径 dfs(nx,ny); path.pop_back(); //出栈，DFS回溯 a[nx][ny]='.'; } } } int main(){ cin >> n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j]; path.push_back(0); a[0][0]='#'; dfs(0,0); return 0; } - 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
3.2 Python代码
下面的Python代码和上面的C++代码逻辑一样。注意它使用栈的方法，用一个list数组 path=[]模拟栈。
def dfs(x,y): if x==n-1 and y==m-1: #到达终点 for i in range(len(path)): print(path[i],end=' ') print() #换行 return dir = ((-1, 0), (0, -1),(1, 0), (0, 1)) #4个方向：左、上、右、下 for u,v in dir: #遍历4个方向的邻居 nx = x+u; ny = y+v #邻居的坐标 if 0<=nx<n and 0<=ny<m and a[nx][ny]=='.': a[nx][ny]='#' #保存现场：这个点在这次更深的dfs中不能再用 path.append(nx*m + ny) #进栈，把这个点记录到路径里 dfs(nx, ny) path.pop(); #出栈，释放这个点 a[nx][ny]='.' #恢复现场：回溯后这个点可以再次用 n,m = map(int, input().split()) #n行、m列 a=[] for i in range(n): #读图，存到二维矩阵a[n][m]，n行m列 a.append(list(input())) path = [] #用栈记录路径 path.append(0) a[0][0]='#' dfs(0,0)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
4、真题
下面的真题，是上面讲解的知识点的直接应用。
路径之谜 2016年第七届决赛，lanqiaoOJ第89题 https://www.lanqiao.cn/problems/89/learning/
【题目描述】小明冒充X星球的骑士，进入了一个奇怪的城堡。城堡里边什么都没有，只有方形石头铺成的地面。假设城堡地面是n×n个方格。按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有n个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
【输入格式】第一行一个整数N(0
又是一道格子搜索题，这种题在蓝桥杯大赛中很常见。
题目要求输出一条路径，用DFS是很合适的，DFS搜索过程中，自然生成一条路径。
每走到一个格子，对应的靶子上箭多一支，靶子上的箭等于给定的数字后，就不用再DFS下去了。这是一个简单的剪枝。
注意DFS时记录路径的技巧。根据题目的要求，用栈来跟踪DFS的过程，记录DFS走过的路径，是最方便的。DFS到某个格子时，把这个格子放到栈里，表示路径增加了这个格子。DFS回溯的时候，退出了这个格子，表示路径上不再包括这个格子，需要从栈中弹走这个格子。4.1 C++代码
#includeusing namespace std; int n; int a[25],b[25],vis[25][25]; vector<int> path; //记录路径 int d[4][2]={1,0,-1,0,0,1,0,-1}; //上下左右 void dfs(int x,int y){ if(a[x]<0 || b[y]<0) return; //剪枝 if(x==n-1 && y==n-1){ //走到出口 int ok=1; for(int i = 0;i < n;i++) if(a[i]!=0 || b[i]!=0){ ok=0; break;} if(ok) for(int i = 0;i < path.size();i++) cout << path[i] <<" "; } for(int i = 0;i < 4;i++){ int tx = x + d[i][0],ty = y + d[i][1]; if(vis[tx][ty]==0 && tx>=0 && tx<n && ty>=0 && ty<n){ vis[tx][ty]=1; path.push_back(tx*n + ty); //进栈，记录路径 a[tx]--; b[ty]--; dfs(tx,ty); path.pop_back(); //出栈，DFS回溯 a[tx]++; b[ty]++; vis[tx][ty]=0; } } } int main(){ cin >> n; for(int i=0;i<n;i++) cin >> b[i]; //北面靶子 for(int i=0;i<n;i++) cin >> a[i]; //西面靶子 path.push_back(0); vis[0][0]=1; a[0]--; b[0]--; dfs(0,0); return 0; } - 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
4.2 Python代码
def dfs(x,y): if a[x]<0 or b[y]<0: return if x==n-1 and y==n-1: ok=1 for i in range(n): if a[i]!=0 or b[i]!=0: ok=0; break if ok==1: for i in range(len(path)): print(path[i],end=' ') for d in [(1,0),(-1,0),(0,1),(0,-1)]: tx = x+d[0]; ty = y+d[1] if 0 <= tx < n and 0 <= ty < n and vis[tx][ty] == 0: vis[tx][ty] = 1 path.append(tx*n + ty) #进栈，记录路径 a[tx] -= 1; b[ty] -= 1 dfs(tx, ty) path.pop(); #出栈，DFS回溯 a[tx] += 1; b[ty] += 1 vis[tx][ty] = 0 n = int(input()) vis = [[0]*n for i in range(n)] path = [] #用栈记录路径 path.append(0) b = list(map(int,input().split())) a = list(map(int,input().split())) vis[0][0]=1 a[0] -= 1; b[0] -= 1 dfs(0,0)- 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
-
相关阅读:
Java秒杀系统设计
Android AssetManager初探
技术总结大杂烩
dubbo学习资料
一种高效且节约内存的聚合数据结构的实现
如何给element el-date-picker日期组件设置时间按照时间禁用
甲板上的战舰|模拟？|每日一题|chatgpt结合更正
XCTF---MISC---Misc文件类型
神经网络 03(参数初始化)
大唐电信FPGA设计经验
- 原文地址：https://blog.csdn.net/weixin_43914593/article/details/127945264
