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

0%

pta-7-52 求解迷宫从入口到出口的所有最短路径(DFS)

求解迷宫从入口到出口的一条最短路径。输入一个迷宫,求从入口通向出口的一条可行最短路径。为简化问题,迷宫用二维数组 int maze[10][10]来存储障碍物的分布,假设迷宫的横向和纵向尺寸的大小是一样的,并由程序运行读入, 若读入迷宫大小的值是n(3<n<=10),则该迷宫横向或纵向尺寸都是n,规定迷宫最外面的一圈是障碍物,迷宫的入口是maze[1][1],出口是maze[n-2][n-2], 若maze[i][j] = 1代表该位置是障碍物,若maze[i][j] = 0代表该位置是可以行走的空位(0<=i<=n-1, 0<=j<=n-1)。求从入口maze[1][1]到出口maze[n-2][n-2]可以走通的所有最短路径条数。要求迷宫中只允许在水平或上下四个方向的空位上行走,走过的位置不能重复走。 如下这样一个迷宫:

对应的二维数组表示:

1
  int maze[10][10]={
2
{1,1,1,1,1,1,1,1,1,1},
3
{1,0,0,1,0,0,0,1,0,1},
4
{1,0,0,1,0,0,0,1,0,1},
5
{1,0,0,0,0,1,1,0,0,1},
6
{1,0,1,1,1,0,0,0,1,1},
7
{1,0,0,0,1,0,0,0,1,1},
8
{1,0,1,0,0,0,1,0,0,1},
9
{1,1,1,1,0,1,1,0,1,1},
10
{1,0,0,0,0,0,0,0,0,1},
11
{1,1,1,1,1,1,1,1,1,1}
12
  };

输入格式:

输入迷宫大小的整数n, 以及n行和n列的二维数组(数组元素1代表障碍物,0代表空位)。

输出格式:

输出按规定可以走通的所有最短路径条数。若没有通路,输出:0。

输入样例:

1
4
2
1 1 1 1
3
1 0 1 1
4
1 0 0 1
5
1 1 1 1

输出样例:

1

输入样例:

1
10
2
1 1 1 1 1 1 1 1 1 1
3
1 0 0 1 0 0 0 1 0 1
4
1 0 0 1 0 0 0 1 0 1
5
1 0 0 0 0 1 1 0 0 1
6
1 0 1 1 1 0 0 0 0 1
7
1 0 0 0 1 0 0 0 0 1
8
1 0 1 0 0 0 1 0 0 1
9
1 0 1 1 1 0 1 1 0 1
10
1 1 0 0 0 0 0 0 0 1
11
1 1 1 1 1 1 1 1 1 1

输出样例:

1

代码:

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