通过深度优先搜索(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递归就先写到这里,之后图论的时候我们在聊。