题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4528
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

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

Problem solving report:

Description: 要去找D和E，D和E是不会动的，"."是路，"X"是墙壁。两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方，看到就是找到了，D和E本身也是一个能遮挡视线的人。
Problem solving: 三维数组对于地图，预处理一下。先对E，D进行处理一下，把可以看到的路径标记为1，看不到的为0，然后就BFS就行了。

Accepted Code:

/* 
 * @Language: C++ 
 * @Author: lzyws739307453 
 * @Date: 2019-08-07 10:01:31 
 * @Last Modified by: lzyws739307453
 * @Last Modified time: 2019-08-07 11:04:01
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
char mp[MAXN][MAXN];
int sgn[2][MAXN][MAXN];
bool vis[2][2][MAXN][MAXN];
int x, y, t, sx, sy, ex, ey, dx, dy;
int dir[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct edge {
    int e, d, x, y, t;
    edge() {}
    edge(int e_, int d_, int x_, int y_, int t_) {
        e = e_, d = d_, x = x_, y = y_, t = t_;
    }
}u, v;
void look(int &a, int &b, int x, int y) {
    a |= sgn[0][x][y];
    b |= sgn[1][x][y];
}
int BFS() {
    queue<edge> Q;
    int se = 0, sd = 0;
    look(se, sd, sx, sy);
    vis[se][sd][sx][sy] = 1;
    Q.push(edge(se, sd, sx, sy, 0));
    while (!Q.empty()) {
        u = Q.front();
        Q.pop();
        look(u.e, u.d, u.x, u.y);
        if (u.e && u.d)
            return u.t;
        for (int i = 0; i < 4; i++) {
            v = edge(u.e, u.d, u.x + dir[i][0], u.y + dir[i][1], u.t + 1);
            if (v.x >= 0 && v.x < x && v.y >= 0 && v.y < y && mp[v.x][v.y] == '.' && !vis[v.e][v.d][v.x][v.y] && v.t <= t) {
                Q.push(v);
                vis[v.e][v.d][v.x][v.y] = 1;
            }
        }
    }
    return -1;
}
void Search(int px, int py, int flag) {
    //向上
    for (int i = px - 1; i >= 0 && mp[i][py] == '.'; i--)
        sgn[flag][i][py] = 1;
    //向下
    for (int i = px + 1; i < x && mp[i][py] == '.'; i++)
        sgn[flag][i][py] = 1;
    //向左
    for (int i = py - 1; i >= 0 && mp[px][i] == '.'; i--)
        sgn[flag][px][i] = 1;
    //向右
    for (int i = py + 1; i < y && mp[px][i] == '.'; i++)
        sgn[flag][px][i] = 1;
}
int main() {
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        scanf("%d%d%d", &x, &y, &t);
        for (int i = 0; i < x; i++) {
            scanf("%s", mp[i]);
            for (int j = 0; j < y; j++) {
                if (mp[i][j] == 'S')
                    mp[sx = i][sy = j] = '.';
                else if (mp[i][j] == 'D')
                    dx = i, dy = j;
                else if (mp[i][j] == 'E')
                    ex = i, ey = j;
            }
        }
        memset(sgn, 0, sizeof(sgn));
        memset(vis, 0, sizeof(vis));
        Search(ex, ey, 0), Search(dx, dy, 1);
        printf("Case %d:\n%d\n", kase, BFS());
    }
    return 0;
}