pta-7-51 迷宫寻路 (20分)DFS

题目

给定一个M行N列的迷宫图，其中 “0”表示可通路，”1”表示障碍物，无法通行。在迷宫中只允许在水平或上下四个方向的通路上行走，走过的位置不能重复走。

5行8列的迷宫如下：

0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0

则从左上角（1，1）至右下角（5，8）的最短路径为：

1,1–》2,1–》2,2–》2,3–》3,3–》3,4–》3,5–》4,5–》5,5–》5,6–》5,7–》5,8

题目保证每个迷宫最多只有一条最短路径。

请输出该条最短路径，如果不存在任何通路，则输出”NO FOUND”.

输入格式：

第一行，输入M和N值，表示迷宫行数和列数。

接着输入M行数值，其中，0表示通路，1表示障碍物。每列数值用空格符间隔。

接下来可能输入多组迷宫数据。

当输入M的值为-1时结束输入。

输出格式：

按行顺序输出路径的每个位置的行数和列数，如 x,y
如果不存在任何路径，则输出”NO FOUND”.
每组迷宫寻路结果用换行符间隔。

输入样例：

8 8	
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4	
0 0 1 0
0 0 0 0
0 0 1 1 
0 1 0 0
-1 -1

输出样例

1,1
2,1
3,1
4,1
5,1
5,2
5,3
6,3
6,4
6,5
7,5
8,5
8,6
8,7
8,8

NO FOUND

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,flag=0,Min;
int Map[100][100];
int vis[100][100];
int dir[4][2]={0,1,0,-1,-1,0,1,0};
int stepA[100][2];//记录当前路径
int stepB[100][2];//记录最短路径 
void dfs(int x,int y,int step){
	if(step>Min){
		return;
	}
	if(x==n&&y==m){
		for(int i=0;i<100;i++){
			if(stepA[i][0]==-1&&stepA[i][1]==-1){
				break;
			}
			stepB[i][0]=stepA[i][0];
			stepB[i][1]=stepA[i][1];
		}
		Min=step;
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(xx<=0||yy<=0||xx>n||yy>m){
			continue;
		}
		if(!vis[xx][yy]&&Map[xx][yy]==0){
			stepA[step][0]=xx;
			stepA[step][1]=yy;
			
			vis[xx][yy]=1;
			dfs(xx,yy,step+1);
			vis[xx][yy]=0;
		}
	}
	return;
}
int main(){
	while(scanf("%d %d",&n,&m)&&m!=-1){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&Map[i][j]);
			}
		}
		memset(vis,0,sizeof(vis));
		memset(stepA,-1,sizeof(stepA));
		memset(stepB,-1,sizeof(stepB));
		vis[1][1]=1;
		Min=10000;
		dfs(1,1,0);
		if(Min==10000){
			printf("NO FOUND\n");
		}
		else{
			printf("1,1\n");
			for(int i=0;i<Min;i++){
				printf("%d,%d\n",stepB[i][0],stepB[i][1]);
			}
			printf("\n");
		}
	}
	return 0;
}