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

0%

Pta-7-50 最近距离 (25分)(DFS)

题目

在一个游戏中,玩家处于一个如下所示12行12列的迷宫:

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

其中迷宫由0,1组成,0表示道路,1表示障碍物。
现在要根据玩家和游戏中被攻击的虚拟boss所在位置,给玩家以最近距离的提示。
最近距离:即玩家走到boss所走的最少步数。(注:路线中的一步是指从一个坐标点走到其上下左右相邻坐标点。)

输入格式:

输入4个整数a,b,c,d(即玩家和虚拟boss在迷宫中的坐标位置分别为(a,b) 、(c,d)), 其中 0<=a,b,c,d<12。

输出格式:

输出在迷宫中从(a,b)出发到达(c,d)的最少步数,如果(a,b)永远无法到达(c,d)则输出10000。

输入样例:

1
0 0 11 11

输出样例

1
22

代码:

1
#include<bits/stdc++.h>
2
using namespace std;
3
int a,b,c,d,flag=0,Min;
4
int Map[12][12]={0,1,0,0,0,1,1,1,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0};
5
int vis[20][20];
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==c&&y==d){
14
		Min=step;
15
		return;
16
	}
17
	for(int i=0;i<4;i++){
18
		int xx=x+dir[i][0];
19
		int yy=y+dir[i][1];
20
		if(xx<0||yy<0||xx>=12||yy>=12){
21
			continue;
22
		}
23
		if(!vis[xx][yy]&&Map[xx][yy]==0){
24
			vis[xx][yy]=1;
25
			dfs(xx,yy,step+1);
26
			vis[xx][yy]=0;
27
		}
28
	}
29
	return;
30
}
31
int main(){
32
	scanf("%d %d %d %d",&a,&b,&c,&d);
33
		memset(vis,0,sizeof(vis));
34
		vis[a][b]=1;
35
		Min=10000;
36
		dfs(a,b,0);
37
		if(Min==10000){
38
			printf("10000\n");
39
		}
40
		else{
41
			printf("%d\n",Min);
42
		}
43
	return 0;
44
}