小明系列故事——捉迷藏
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 609 Accepted Submission(s): 141
Problem Description
小明的妈妈生了三个孩子，老大叫大明， 老二叫二明， 老三...， 老三自然就叫小明了。
一天，小明的妈妈带小明兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身， 于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小明来找其他两个人，游戏规则很简单：
只要小明可以在规定的时间内找到他们就算小明获胜，并且被发现的两个人猜拳决定谁在下一轮负责找人；如果在规定的时间内只找到一个人，那么没有被发现的人获胜，被找到的人下一轮负责找人；如果在规定的时间内一个人都没有找到，则小明失败了，下一轮还是他来找人。现在小明想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。
为了简单起见，把公园看成是n行m列的矩阵，其中’S’表示小明，’D’表示大名，’E’表示二明，’X’表示障碍物，’.’表示通路。这里，我们把发现定义为，可以直接看到对方， 也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。并且假设，大明，二明藏好以后就不会再改变位置，小明每个单位时间可以从当前的位置走到相邻的四个位置之一，并且不会走出公园。
一天，小明的妈妈带小明兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身， 于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小明来找其他两个人，游戏规则很简单：
只要小明可以在规定的时间内找到他们就算小明获胜，并且被发现的两个人猜拳决定谁在下一轮负责找人；如果在规定的时间内只找到一个人，那么没有被发现的人获胜，被找到的人下一轮负责找人；如果在规定的时间内一个人都没有找到，则小明失败了，下一轮还是他来找人。现在小明想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。
为了简单起见，把公园看成是n行m列的矩阵，其中’S’表示小明，’D’表示大名，’E’表示二明，’X’表示障碍物，’.’表示通路。这里，我们把发现定义为，可以直接看到对方， 也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。并且假设，大明，二明藏好以后就不会再改变位置，小明每个单位时间可以从当前的位置走到相邻的四个位置之一，并且不会走出公园。
Input
测试数据第一行是一个正整数T，表示有T组测试数据。
每一组测试数据首先是三个正整数n,m,t，分别表示行数、列数和规定的时间，接下来n行，每行m个上述的字符，并且保证有且只有一个’S’，一个’E’，一个’D’。
每一组测试数据首先是三个正整数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。
接下来一行，如果小明可以在规定时间内找到所有的人，则输出最少需要的时间，否则输出-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
Source
Recommend
liuyiding
题目大意：中文题，不解释。
题目分析：要在t步之内找到另外2个人，每个点4个状态（想一想，为什么）。首先对地图进行预处理，0-3表示能走，同时也表示了一个点的4种状态。然后就是简单的bfs了。
详情请见代码：
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105;
const int M = 100005;//减2个0 15MS 336K
int m,n,t;
int si,sj,di,dj,ei,ej;
int mp[N][N];
bool flag[N][N][2][2];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
struct node
{
int x,y,step;
bool d,e;
}ss,now;
struct que
{
node t[M];
int head,tail;
void init()
{
head = tail = 0;
}
bool empty()
{
return head == tail;
}
struct node top()
{
return t[head];
}
void pop()
{
head ++;
if(head >= M)
head -= M;
}
void push(struct node a)
{
t[tail] = a;
tail ++;
if(tail >= M)
tail -= M;
}
}q;
bool isok(int x,int y)
{
return (x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != 7 && mp[x][y] <= 3);
}
void predeal()
{
int i,tx,ty;
for(i = 0;i < 4;i ++)
{
tx = di + dx[i];
ty = dj + dy[i];
while(isok(tx,ty))
{
mp[tx][ty] += 1;
tx += dx[i];
ty += dy[i];
}
tx = ei + dx[i];
ty = ej + dy[i];
while(isok(tx,ty))
{
mp[tx][ty] += 2;
tx += dx[i];
ty += dy[i];
}
}
}
void bfs()
{
q.init();
ss.x = si;
ss.y = sj;
ss.step = 0;
memset(flag,false,sizeof(flag));
switch(mp[si][sj])
{
case 0:ss.d = ss.e = false;break;
case 1:ss.d = true;ss.e = false;break;
case 2:ss.d = false;ss.e = true;break;
case 3:ss.d = ss.e = true;break;
}
if(ss.d && ss.e)
{
printf("0\n");
return;
}
int i;
flag[si][sj][ss.d][ss.e] = true;
q.push(ss);
while(!q.empty())
{
now = q.top();
q.pop();
if(now.step > t)
{
printf("-1\n");
return;
}
for(i = 0;i < 4;i ++)
{
ss = now;
ss.x += dx[i];
ss.y += dy[i];
ss.step ++;
if(isok(ss.x,ss.y) && !flag[ss.x][ss.y][ss.d][ss.e])
{
flag[ss.x][ss.y][ss.d][ss.e] = true;
switch(mp[ss.x][ss.y])
{
case 1:ss.d = true;break;
case 2:ss.e = true;break;
case 3:ss.d = ss.e = true;break;
}
if(ss.d && ss.e && ss.step <= t)
{
printf("%d\n",ss.step);
return;
}
q.push(ss);
}
}
}
printf("-1\n");
}
int main()
{
int i,j,T;
char c;
int cas = 0;
scanf("%d",&T);
while(T --)
{
scanf("%d%d%d",&n,&m,&t);
getchar();
for(i = 1;i <= n;i ++)
{
for(j = 1;j <= m;j ++)
{
c = getchar();
switch(c)
{
case 'X':mp[i][j] = 7;break;
case '.':mp[i][j] = 0;break;
case 'D':mp[i][j] = 4;di = i;dj = j;break;
case 'E':mp[i][j] = 5;ei = i;ej = j;break;
case 'S':mp[i][j] = 0;si = i;sj = j;break;
}
}
getchar();
}
predeal();//
printf("Case %d:\n",++ cas);
bfs();
}
return 0;
}
//15MS 440K
/*
8
5 6 3
XXD...
....E.
....X.
....S.
......
5 6 3
XDX...
....E.
......
....S.
......
5 6 8
XXDX..
.XEX..
......
....S.
......
4 4 8
S...
.X..
..XD
...E
4 4 9
S...
.X..
..XD
...E
*/