2447 - C：迷宫逃出
我的名字是工藤新一
是解决困难案件的高中生名侦探
可是有一天被神秘的组织灌下了毒药
身体缩小了
变成了江户川柯南
身体虽然变小
头脑还是一样
不管什么案件
真相永远只有一个
——江户川柯南
为了躲避黑暗组织的追踪，柯南不慎逃入一个远古的迷宫，机智的柯南马上通过卫星电话手表从阿笠博士那获取了迷宫地图。不幸的是，迷宫的出口有3个钥匙插槽，必须同时集齐这3把不同的钥匙才能打开出口的门。而这3把钥匙分别分布在迷宫中不同的地方。
假设只有移动需要时间，柯南只能上下左右移动，并且每秒只能移动一格，迷宫中的墙壁无法穿越。柯南再不逃离，黑暗组织就要追进来了。他能逃离吗？如果能，最快需要多少秒才能打开出口逃离迷宫呢？
Input
输入数据的第一行是一个整数T，表示有T组测试样例，接着是T块数据，每块数据先是两个整数n和m，分别表示迷宫的行数和列数，接着是个n行m列的字符矩阵表示迷宫地图，一个字符代表迷宫一格，’S’表示柯南当前所在地，’D’表示出口，’.’表示普通的路，’*’表示墙壁，’A’、’B’、’C’分别表示3把不同的钥匙。T<=10，2<n,m<=20。
Output
对于每组测试样例，如果柯南可以逃离，输出柯南逃离迷宫所需最短时间并独占一行；如果柯南无法逃离，输出-1并独占一行。
<br />
Examples
Input
2 3 3 D.C *.. SAB 4 3 D*A ..* S.B .C.
Output
6 -1
Solution 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; }