游客 注册 | 登录
中文 | En

2447 - C：迷宫逃出

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

我的名字是工藤新一
是解决困难案件的高中生名侦探
可是有一天被神秘的组织灌下了毒药
身体缩小了
变成了江户川柯南
身体虽然变小
头脑还是一样
不管什么案件
真相永远只有一个
——江户川柯南

为了躲避黑暗组织的追踪，柯南不慎逃入一个远古的迷宫，机智的柯南马上通过卫星电话手表从阿笠博士那获取了迷宫地图。不幸的是，迷宫的出口有3个钥匙插槽，必须同时集齐这3把不同的钥匙才能打开出口的门。而这3把钥匙分别分布在迷宫中不同的地方。
假设只有移动需要时间，柯南只能上下左右移动，并且每秒只能移动一格，迷宫中的墙壁无法穿越。柯南再不逃离，黑暗组织就要追进来了。他能逃离吗？如果能，最快需要多少秒才能打开出口逃离迷宫呢？

题目输入

输入数据的第一行是一个整数T，表示有T组测试样例，接着是T块数据，每块数据先是两个整数n和m，分别表示迷宫的行数和列数，接着是个n行m列的字符矩阵表示迷宫地图，一个字符代表迷宫一格，’S’表示柯南当前所在地，’D’表示出口，’.’表示普通的路，’*’表示墙壁，’A’、’B’、’C’分别表示3把不同的钥匙。T<=10，2<n,m<=20。

题目输出


对于每组测试样例，如果柯南可以逃离，输出柯南逃离迷宫所需最短时间并独占一行；如果柯南无法逃离，输出-1并独占一行。

<br />

输入/输出样例

输入格式

2
3 3
D.C
*..
SAB
4 3
D*A
..*
S.B
.C.

输出格式

6
-1

C++解答

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int n,m,mark;
const int inf=100000000;
char a[101][101];
int b[5][5],flag[101][101];
int dre[4][2]={1,0,0,1,-1,0,0,-1};
struct node
{
	int x,y,t;
}p;
int bfs(int sx,int sy,int dx,int dy)
{
	queue<node> q;
	int x,y,t,u,v,i;
	memset(flag,0,sizeof(flag));
	p.x=sx;
	p.y=sy;
	p.t=0;
	flag[sx][sy]=1;
	q.push(p);
	while(!q.empty())
	{
		p=q.front();
		q.pop();
		x=p.x;
		y=p.y;
		t=p.t;
		if(x==dx&&y==dy)
			return t;
		for(i=0;i<4;i++)
		{
			u=x+dre[i][0];
			v=y+dre[i][1];
			if(u>=0&&u<n&&v>=0&&v<m&&a[u][v]!='*'&&flag[u][v]==0)
			{
				flag[u][v]=1;
				p.x=u;
				p.y=v;
				p.t=t+1;
				q.push(p);
			}
		}
	}
	mark=1;
	return -1;
}
int main()
{
	int i,j,k,T,min;
	int x[5],y[5],s[6];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%*c",&n,&m);
		for(i=0;i<n;i++)
		{
			scanf("%s",a[i]);
			for(j=0;j<m;j++)
				if(a[i][j]=='S')
				{
					x[0]=i;
					y[0]=j;
				}
				else if(a[i][j]=='A')
				{
					x[1]=i;
					y[1]=j;
				}
				else if(a[i][j]=='B')
				{
					x[2]=i;
					y[2]=j;
				}
				else if(a[i][j]=='C')
				{
					x[3]=i;
					y[3]=j;
				}
				else if(a[i][j]=='D')
				{
					x[4]=i;
					y[4]=j;
				}
		}
		mark=0;
		for(i=0;i<5;i++)
		{
			for(j=0;j<=i;j++)
			{
				if(j==0&&i==4)
				{
					b[i][j]=b[j][i]=inf;
					continue;
				}
				else if(i==j)
				{
					b[i][j]=0;
					continue;
				}
				b[i][j]=b[j][i]=bfs(x[i],y[i],x[j],y[j]);
				if(mark)
					break;
			}
			if(mark)
				break;
		}
		if(mark)
		{
			printf("-1\n");
			continue;
		}
		min=inf;
		s[0]=b[0][1]+b[1][2]+b[2][3]+b[3][4];
		s[1]=b[0][1]+b[1][3]+b[3][2]+b[2][4];
		s[2]=b[0][2]+b[2][1]+b[1][3]+b[3][4];
		s[3]=b[0][2]+b[2][3]+b[3][1]+b[1][4];
		s[4]=b[0][3]+b[3][1]+b[1][2]+b[2][4];
		s[5]=b[0][3]+b[3][2]+b[2][1]+b[1][4];
		for(i=0;i<6;i++)
			if(s[i]<min)
				min=s[i];
		printf("%d\n",min);
	}
	return 0;
}
请先登陆