题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4528
小明系列故事——捉迷藏
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1464 Accepted Submission(s): 423
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.
......
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
-1
Case 2:
3
Case 3:
-1
Source
第一次做这种BFS，学了一些东西。主要是参考了syhjh的思路和方法。
总结一下吧：
和普通的宽搜不相同的地方，1,两个目标，2，有步数限制(其实就是个优化咯)
怎么写呢？ 结构体中不仅有x,y坐标，time步数，还要有这连个目标是否找到，一个一个的找，宽搜的时候把前一个状态复制过来，结束宽搜的语句就很好写了。然后就是判环(就是不走重复路，mark数组可以4维也可以二维)，
然后还有一点很重要，就是样例中的第三个样例，说明了小明不能穿过D,E，所以在初始化的时候就记录下这两个点，然后变为不可走的点。
最后做一下BFS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 111
#define inf 1<<30
struct Node
{
int x,y;
int time;
bool tag1,tag2;
};
int n,m,time,ans;
Node st,ed1,ed2;
char maps[MAXN][MAXN];
bool mark[MAXN][MAXN][][];
int dir[][]= {{-,},{,},{,-},{,}}; bool Judge(Node &p)
{
int x=p.x,y=p.y;
if(x==ed1.x)
{
for(int i=y+; i<=m; i++)
{
if(ed1.y==i)
{
p.tag1=true;
break;
}
else if(maps[x][i]=='X')break;
}
for(int i=y-; i>=; i--)
{
if(ed1.y==i)
{
p.tag1=true;
break;
}
else if(maps[x][i]=='X')break;
}
}
if(x==ed2.x)
{
for(int i=y+; i<=m; i++)
{
if(ed2.y==i)
{
p.tag2=true;
break;
}
else if(maps[x][i]=='X')break;
}
for(int i=y-; i>=; i--)
{
if(ed2.y==i)
{
p.tag2=true;
break;
}
else if(maps[x][i]=='X')break;
}
}
if(y==ed1.y)
{
for(int i=x+; i<=n; i++)
{
if(ed1.x==i)
{
p.tag1=true;
break;
}
else if(maps[i][y]=='X')break;
}
for(int i=x-; i>=; i--)
{
if(ed1.x==i)
{
p.tag1=true;
break;
}
else if(maps[i][y]=='X')break;
}
}
if(y==ed2.y)
{
for(int i=x+; i<=n; i++)
{
if(ed2.x==i)
{
p.tag2=true;
break;
}
else if(maps[i][y]=='X')break;
}
for(int i=x-; i>=; i--)
{
if(ed2.x==i)
{
p.tag2=true;
break;
}
else if(maps[i][y]=='X')break;
}
}
if(p.tag1&&p.tag2)return true;
return false;
} void bfs()
{
memset(mark,false,sizeof(mark));
queue<Node>Q;
Node p,q;
mark[st.x][st.y][st.tag1][st.tag2]=true;
Q.push(st);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(Judge(p))ans=min(ans,p.time);
if(p.time>time)continue; ///you hua
for(int i=; i<; i++)
{
q=p;
q.x=p.x+dir[i][];
q.y=p.y+dir[i][];
if(q.x<||q.x>n||q.y<||q.y>m||maps[q.x][q.y]=='X')
continue;
if(!mark[q.x][q.y][q.tag1][q.tag2])
{
mark[q.x][q.y][q.tag1][q.tag2]=true;
q.time++;
Q.push(q);
}
}
}
} int main()
{
int _case,t=;
scanf("%d",&_case);
while(_case--)
{
scanf("%d%d%d",&n,&m,&time);
for(int i=; i<=n; i++)
{
scanf("%s",maps[i]+);
for(int j=; j<=m; j++)
{
if(maps[i][j]=='S')
{
st.x=i,st.y=j,st.tag1=st.tag2=false,st.time=;
}
else if(maps[i][j]=='E')
{
ed1.x=i,ed1.y=j;
maps[i][j]='X';
}
else if(maps[i][j]=='D')
{
maps[i][j]='X';
ed2.x=i,ed2.y=j;
}
}
}
ans=inf;
bfs();
printf("Case %d:\n",t++);
if(ans<=time)
{
printf("%d\n",ans);
}
else
puts("-1");
}
return ;
}