2013腾讯马拉松初赛 ACM 小明系列故事——捉迷藏

[c]代码库

/*

2013腾讯马拉松初赛第5场

1004 小明系列故事——捉迷藏
 
Time Limit: 0.2 Seconds   Memory Limit: 32768K
 

小明的妈妈生了三个孩子，老大叫大明， 老二叫二明， 老三...， 老三自然就叫小明了。
一天，小明的妈妈带小明兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身， 于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小明来找其他两个人，游戏规则很简单：
只要小明可以在规定的时间内找到他们就算小明获胜，并且被发现的两个人猜拳决定谁在下一轮负责找人；如果在规定的时间内只找到一个人，那么没有被发现的人获胜，被找到的人下一轮负责找人；如果在规定的时间内一个人都没有找到，则小明失败了，下一轮还是他来找人。现在小明想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。
为了简单起见，把公园看成是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 <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef  __int64 LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
const int maxn = 100 + 20;
const int mod  = 1000000000 + 7;
char ma[maxn][maxn];
bool vis[maxn][maxn][2][2];
struct node {
    int x, y, step;
    int f1, f2;
} s_pos, d_pos, e_pos;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m, t;
void cheak(node &a, node b) {
    if(a.x == b.x) {
        int start = min(a.y, b.y), end = max(a.y, b.y), find = 0;
        for(int i = start + 1; i < end; i++) {
            if(ma[a.x][i] != '.') {
                find = 1;
                break;
            }
        }
        if(!find) {
            a.f1 = 1;
        }
    }
    if(a.y == b.y) {
        int start = min(a.x, b.x), end = max(a.x, b.x), find = 0;
        for(int i = start + 1; i < end; i++) {
            if(ma[i][a.y] != '.') {
                find = 1;
                break;
            }
        }
        if(!find) {
            a.f1 = 1;
        }
    }

}
void cheak2(node &a, node b) {
    if(a.x == b.x) {
        int start = min(a.y, b.y), end = max(a.y, b.y), find = 0;
        for(int i = start + 1; i < end; i++) {
            if(ma[a.x][i] != '.') {
                find = 1;
                break;
            }
        }
        if(!find) {
            a.f2 = 1;
        }
    }
    if(a.y == b.y) {
        int start = min(a.x, b.x), end = max(a.x, b.x), find = 0;
        for(int i = start + 1; i < end; i++) {
            if(ma[i][a.y] != '.') {
                find = 1;
                break;
            }
        }
        if(!find) {
            a.f2 = 1;
        }
    }

}
int bfs() {
    memset(vis, false, sizeof(vis));
    queue<node> q;
    cheak(s_pos, d_pos);
    cheak2(s_pos, e_pos);
    vis[s_pos.x][s_pos.y][s_pos.f1][s_pos.f2] = true;

    q.push(s_pos);
    while(!q.empty()) {
        node now = q.front();
        q.pop();
        if(now.f1 > 0 && now.f2 > 0) {
            return now.step;
        }
        for(int i = 0; i < 4; i++) {
            node next = now;
            next.x += dx[i];
            next.y += dy[i];
            if(next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && !vis[next.x][next.y][next.f1][next.f2]
                    && ma[next.x][next.y] == '.') {
                vis[next.x][next.y][next.f1][next.f2] = true;
                next.step++;
                if(!next.f1)
                    cheak(next, d_pos);

                if(!next.f2)
                    cheak2(next, e_pos);
                if(next.step <= t)
                    q.push(next);

            }
        }
    }
    return 10000;
}
int main() {
    int  T, ca = 1;
    cin >> T;
    while(T--) {
        scanf("%d %d %d", &n, &m, &t);
        for(int i = 0; i < n; i++)
            scanf("%s", ma[i]);

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(ma[i][j] == 'S') {
                    s_pos.x = i;
                    s_pos.y = j;
                    s_pos.step = 0;
                    s_pos.f1 = s_pos.f2 = 0;
                }
                if(ma[i][j] == 'D') {
                    d_pos.x = i;
                    d_pos.y = j;
                }
                if(ma[i][j] == 'E') {
                    e_pos.x = i;
                    e_pos.y = j;
                }
            }
        }
        int now = bfs();
        printf("Case %d:\n", ca++);
        if(now <= t) printf("%d\n", now);
        else       printf("-1\n");

    }
    return 0;
}