题目链接:传送门
Problem Description
小明的妈妈生了三个孩子,老大叫大明, 老二叫二明, 老三..., 老三自然就叫小明了。
一天,小明的妈妈带小明兄弟三人去公园玩耍,公园里面树木很多,有很多地方可以藏身, 于是他们决定玩捉迷藏。经过几轮的猜拳后,第一轮是小明来找其他两个人,游戏规则很简单:
只要小明可以在规定的时间内找到他们就算小明获胜,并且被发现的两个人猜拳决定谁在下一轮负责找人;如果在规定的时间内只找到一个人,那么没有被发现的人获胜,被找到的人下一轮负责找人;如果在规定的时间内一个人都没有找到,则小明失败了,下一轮还是他来找人。现在小明想知道,在规定时间内,自己是否可以找到所有的人,现在他想请你来帮忙计算一下。
为了简单起见,把公园看成是n行m列的矩阵,其中’S’表示小明,’D’表示大名,’E’表示二明,’X’表示障碍物,’.’表示通路。这里,我们把发现定义为,可以直接看到对方, 也就是说两个人在同一行或者同一列,并且中间没有障碍物或者没有其他人就可以看到对方。并且假设,大明,二明藏好以后就不会再改变位置,小明每个单位时间可以从当前的位置走到相邻的四个位置之一,并且不会走出公园。
Input
测试数据第一行是一个正整数T,表示有T组测试数据。
每一组测试数据首先是三个正整数n,m,t,分别表示行数、列数和规定的时间,接下来n行,每行m个上述的字符,并且保证有且只有一个’S’,一个’E’,一个’D’。
[Technical Specification]
T < 200
3 <= n, m <= 100
0 <= t <= 100
Output
每组先输出一行Case c:(c表示当前的组数,从1开始计数);
接下来一行,如果小明可以在规定时间内找到所有的人,则输出最少需要的时间,否则输出-1。
Sample Input
3
5 6 3
XXD...
....E.
....X.
....S.
......
5 6 3
XDX...
....E.
......
....S.
......
5 6 8
XXDX..
.XEX..
......
....S.
......
Sample Output
Case 1:
-1
Case 2:
3
Case 3:
-1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
char m[105][105];
int n[105][105][3][3];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int w,s,tim;
int x1,y1;
struct nate
{
int a,b,t,x,y;
};
void qur(nate &cur)
{
int a,b,c,d;
for(a=0;a<4;a++)
{
c=cur.x;
d=cur.y;
while(1)
{
c=c+dir[a][0];
d=d+dir[a][1];
if(c<0||c>=w||d<0||d>=s)
break;
if(m[c][d]=='D')
{
cur.a=1;
break;
}
if(m[c][d]=='E')
{
cur.b=1;
break;
}
if(m[c][d]=='X')
break;
}
}
}
int bfs()
{
nate next,rent;
queue<nate>q;
rent.x=x1;
rent.y=y1;
rent.a=0;
rent.b=0;
rent.t=0;
q.push(rent);
memset(n,0,sizeof(n));
n[x1][y1][0][0]=1;
int a,b,c,d;
while(!q.empty())
{
rent=q.front();
q.pop();
qur(rent);
if(rent.a==1&&rent.b==1)
return rent.t;
if(rent.t>=tim)
continue;
for(a=0;a<4;a++)
{
next.x=rent.x+dir[a][0];
next.y=rent.y+dir[a][1];
next.t=rent.t+1;
next.a=rent.a;
next.b=rent.b;
if(next.x<0||next.x>=w||next.y<0||next.y>=s)
continue;
if(n[next.x][next.y][next.a][next.b])
continue;
if(m[next.x][next.y]!='.')
continue;
n[next.x][next.y][next.a][next.b]=1;
q.push(next);
}
}
return -1;
}
int main()
{
int a,b,c,d,e,f;
cin>>a;
f=0;
while(a--)
{
cin>>w>>s>>tim;
for(b=0;b<w;b++)
{
for(c=0;c<s;c++)
{
cin>>m[b][c];
if(m[b][c]=='S')
{
x1=b;
y1=c;
}
}
}
e=bfs();
printf("Case %d:\n",++f);
cout<<e<<endl;
}
return 0;
}