Life has its own fate, and meeting may not be accidental.

0%

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

题目

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

5行8列的迷宫如下:

1
0 1 1 1 0 0 0 0
2
0 0 0 1 0 0 0 0
3
0 1 0 0 0 1 0 0
4
0 1 1 1 0 1 1 0
5
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”.
每组迷宫寻路结果用换行符间隔。

输入样例:

1
8 8	
2
0 0 1 0 0 0 1 0
3
0 0 1 0 0 0 1 0
4
0 0 0 0 1 1 0 0
5
0 1 1 1 0 0 0 0
6
0 0 0 1 0 0 0 0
7
0 1 0 0 0 1 0 0
8
0 1 1 1 0 1 1 0
9
1 0 0 0 0 0 0 0
10
4 4	
11
0 0 1 0
12
0 0 0 0
13
0 0 1 1 
14
0 1 0 0
15
-1 -1

输出样例

1
1,1
2
2,1
3
3,1
4
4,1
5
5,1
6
5,2
7
5,3
8
6,3
9
6,4
10
6,5
11
7,5
12
8,5
13
8,6
14
8,7
15
8,8
16
17
NO FOUND

代码:

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,m,flag=0,Min;
4
int Map[100][100];
5
int vis[100][100];
6
int dir[4][2]={0,1,0,-1,-1,0,1,0};
7
int stepA[100][2];//记录当前路径
8
int stepB[100][2];//记录最短路径 
9
void dfs(int x,int y,int step){
10
	if(step>Min){
11
		return;
12
	}
13
	if(x==n&&y==m){
14
		for(int i=0;i<100;i++){
15
			if(stepA[i][0]==-1&&stepA[i][1]==-1){
16
				break;
17
			}
18
			stepB[i][0]=stepA[i][0];
19
			stepB[i][1]=stepA[i][1];
20
		}
21
		Min=step;
22
		return;
23
	}
24
	for(int i=0;i<4;i++){
25
		int xx=x+dir[i][0];
26
		int yy=y+dir[i][1];
27
		if(xx<=0||yy<=0||xx>n||yy>m){
28
			continue;
29
		}
30
		if(!vis[xx][yy]&&Map[xx][yy]==0){
31
			stepA[step][0]=xx;
32
			stepA[step][1]=yy;
33
			
34
			vis[xx][yy]=1;
35
			dfs(xx,yy,step+1);
36
			vis[xx][yy]=0;
37
		}
38
	}
39
	return;
40
}
41
int main(){
42
	while(scanf("%d %d",&n,&m)&&m!=-1){
43
		for(int i=1;i<=n;i++){
44
			for(int j=1;j<=m;j++){
45
				scanf("%d",&Map[i][j]);
46
			}
47
		}
48
		memset(vis,0,sizeof(vis));
49
		memset(stepA,-1,sizeof(stepA));
50
		memset(stepB,-1,sizeof(stepB));
51
		vis[1][1]=1;
52
		Min=10000;
53
		dfs(1,1,0);
54
		if(Min==10000){
55
			printf("NO FOUND\n");
56
		}
57
		else{
58
			printf("1,1\n");
59
			for(int i=0;i<Min;i++){
60
				printf("%d,%d\n",stepB[i][0],stepB[i][1]);
61
			}
62
			printf("\n");
63
		}
64
	}
65
	return 0;
66
}