算法基础③
2022/4/6 20:49:15
本文主要是介绍算法基础③,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
迷宫问题
通过深度优先搜索(DFS)方法实现。
迷宫问题一
一天蒜头君掉进了一个迷宫里面,蒜头君想逃出去,可怜的蒜头君连迷宫是否有能逃出去的路都不知道。 看在蒜头君这么可怜的份上,就请聪明的你告诉蒜头君是否有可以逃出去的路。 输入格式 第一行输入两个整数 nn 和 mm,表示这是一个 n \times mn×m 的迷宫。 接下来的输入一个 nn 行 mm 列的迷宫。其中 'S' 表示蒜头君的位置,'*'表示墙,蒜头君无法通过,'.'表示路,蒜头君可以通过'.'移动,'T'表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。 输出格式 输出一个字符串,如果蒜头君可以逃出迷宫输出"yes",否则输出"no"。 数据范围 1 \le n, m \le 101≤n,m≤10。 输出时每行末尾的多余空格,不影响答案正确性 样例输入1复制 3 4 S**. ..*. ***T 样例输出1复制 no 样例输入2复制 3 4 S**. .... ***T 样例输出2复制 yes
题解
我们读入所有数据,然后获得起点S的坐标。然后深度优先遍历,在迷宫问题中进入DFS后,要先判断是否到中点,在判断是否是障碍物,然后标记该点访问过了。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=15; int n,m; char g[N][N]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; bool st[N][N]; bool dfs(int x,int y){ if(g[x][y]=='T'){ return true; } if(g[x][y]=='*') return false; st[x][y]=true; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>n||a<=0||b<=0||b>m)continue; if(st[a][b])continue; if(dfs(a,b)){ return true; } } return false; } int main(){ cin>>n>>m; int x,y; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; if(g[i][j]=='S'){ x=i; y=j; } } } if(dfs(x,y)){ cout<<"yes"<<endl; }else{ cout<<"no"<<endl; } return 0; }
迷宫问题二
蒜头君在你的帮助下终于逃出了迷宫,但是蒜头君并没有沉浸于喜悦之中,而是很快的又陷入了思考,从这个迷宫逃出的最少步数是多少呢? 输入格式 第一行输入两个整数 nn 和 mm,表示这是一个 n \times mn×m 的迷宫。 接下来的输入一个 nn 行 mm 列的迷宫。其中 'S' 表示蒜头君的位置,'*'表示墙,蒜头君无法通过,'.'表示路,蒜头君可以通过'.'移动,'T'表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。 输出格式 输出整数,表示蒜头君逃出迷宫的最少步数,如果蒜头君无法逃出迷宫输出 -1−1。 数据范围 1 \le n, m \le 101≤n,m≤10。 输出时每行末尾的多余空格,不影响答案正确性 样例输入1复制 3 4 S**. ..*. ***T 样例输出1复制 -1 样例输入2复制 3 4 S**. .... ***T 样例输出2复制 5
题解
本题要求判断是否可以到达并且要计算出最短路径,其实用宽度优先搜索更为合适,因为宽度优先搜索第一次到达目的地就是最短路径,但是我们使用深度优先也可以实现,我们定义一个最短量来储存最短的路径,当每一次到达目的点就比较一下与最短路的大小,交换最短路径长度,因此我们要遍历所有的可行路径,所以就要回溯访问状态,所以在一个遍历后就要复原,将一个点置为未访问,额额额,在 这道题中,我开始忘了读入n和m所以出现了segment段错误,还检查了好久没查到。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=15; char g[N][N]; bool st[N][N]; int Min=99999; int m,n; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; void dfs(int x,int y,int stmp){ if(stmp>Min) return ; if(g[x][y]=='T'){ Min=min(Min,stmp); return; } st[x][y]=true; if(g[x][y]=='*') return ; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>n||a<=0||b>m||b<=0) continue; if(st[a][b]) continue; if(g[a][b]=='*') continue; dfs(a,b,stmp+1); st[a][b]=false; } } int main(){ cin>>n>>m; int a,b; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; if(g[i][j]=='S'){ a=i,b=j; } } } dfs(a,b,0); if(Min==99999){ cout<<-1<<endl; }else{ cout<<Min<<endl; } return 0; }
迷宫问题三
经过思考蒜头君终于解决了怎么计算一个迷宫的最短路问题,于是蒜头君找到一个新的迷宫图,来验证自己是否真的会计算一个迷宫的最短路。 为了检验自己计算的是否正确,蒜头君特邀你一起来计算。 输入格式 第一行输入两个整数 nn 和 mm,表示这是一个 n \times mn×m 的迷宫。 接下来的输入一个 nn 行 mm 列的迷宫。其中'@'表示蒜头君的位置,'#'表示墙,蒜头君无法通过,'.'表示路,蒜头君可以通过'.'移动,所有在迷宫最外围的'.'都表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。 输出格式 输出整数,表示蒜头君逃出迷宫的最少步数,如果蒜头君无法逃出迷宫输出 -1−1。 数据范围 1 \le n,m \le 151≤n,m≤15。 输出时每行末尾的多余空格,不影响答案正确性 样例输入1复制 9 13 ############# #@..........# #####.#.#.#.# #...........# #.#.#.#.#.#.# #.#.......#.# #.#.#.#.#.#.# #...........# #####.####### 样例输出1复制 11 样例输入2复制 4 6 #.#### #.#.## #...@# ###### 样例输出2复制 5
题解
该迷宫问题与第二个迷宫问题类似,我们也要求出最短路径,所以一样要使用minn记录短的路径。
但是这个题要注意到达的条件,和第二个迷宫终点判断不一样,这个题要观察迷宫的构造,判断终止条件。所以这道题尽量从1开始存储迷宫图。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=20; int n,m; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; char g[N][N]; bool st[N][N]; int minn=99999; void dfs(int x,int y,int stmp){ if(stmp>minn)return ; if(x==0||y==0||x==n+1||y==m+1){ minn=min(minn,stmp); return ; } st[x][y]=true; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(g[a][b]=='#')continue; if(st[a][b])continue; dfs(a,b,stmp+1); st[a][b]=false; } } int main(){ cin>>n>>m; int x,y; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; if(g[i][j]=='@'){ x=i;y=j; } } } dfs(x,y,0); if(minn==99999){ cout<<-1<<endl; }else{ cout<<minn-1<<endl; } return 0; }
好了,dfs递归就先写到这里,之后图论的时候我们在聊。
递推
这篇关于算法基础③的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现