hdu Kaitou Kid The Phantom Thief (2)

Kaitou Kid - The Phantom Thief (2)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 67 Accepted Submission(s): 39

Problem Description

破解字迷之后，你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石，并离开展馆。整个展馆呈矩形分布，划分为N*M个区域，有唯一的入口和出口（不能从出口进入，同样不能从入口出去）。由某个区域可直接移动至相邻四个区域中的一个，且最快需要一分钟。假设Kid进入放有宝石的区域即可盗取宝石，无需耗时。问至少要封锁几个区域（可以封锁放有宝石的区域，但不能封锁入口和出口）才能保证Kid无法完成任务。

Input

输入的第一行有一个整数C，代表有C组测试数据。每组测试数据的第一行有三个整数N，M，T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图，其中包括：
'S'：入口 'E'：出口 'J'：放有宝石的区域，至少出现一次 '.'：空白区域 '#'：墙

Output

对每组测试数据，输出至少要封锁的区域数。

Sample Input

2
5 5 5
SJJJJ
..##J
.JJJJ
.J...
EJ...
5 5 6
SJJJJ
..##J
.JJJJ
.J...

EJ...

Sample Output

0
2

Author

Source

2008杭电集训队选拔赛

Recommend

wangye

分析：最多封锁4个位置，所以从0枚举到3，直到KID无法完成任务。判断能否完成任务时，每个位置可能有两种情况：有无拿到宝石，这样设置一个二维的标记数组就能将回头的bfs转化为了不能回头的。如果直接用不回头的bfs法会MLE。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

typedef struct S {
    int order, time, J;
} STEP;
char map[100], s[10];
int m, n, start;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int vis[2][100];
int t;

int bfs() {
    int k, i, j, xx, yy, temp;
    STEP now, next;
    now.order = start;
    now.time = 0;
    now.J = 0;
    queue<STEP> q;
    memset(vis, 0, sizeof (vis));
    vis[0][start] = 1;
    q.push(now);
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (now.time >= t)
            continue;
        i = now.order / n;
        j = now.order % n;
        for (k = 0; k < 4; ++k) {
            xx = i + dx[k];
            yy = j + dy[k];
            temp = xx * n + yy;
            next.time = now.time + 1;
            if (xx >= 0 && xx < m && yy >= 0 && yy < n) {
                if (map[temp] == 'E') {
                    if (now.J)
                        return 0;
                }
                if (map[temp] != '#') {
                    if (map[temp] == 'J')
                        next.J = 1;
                    else
                        next.J = now.J;
                    if (!vis[now.J][temp]) {
                        vis[now.J][temp] = 1;
                        next.order = temp;
                        q.push(next);
                    }
                }
            }
        }
    }
    return 1;
}

int main() {
    int i, j, jd, T, ans;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &m, &n, &t);
        scanf("%*c");
        jd = 0;
        for (i = 0; i < m; ++i) {
            scanf("%s", s);
            for (j = 0; j < n; ++j) {
                map[jd + j] = s[j];
                if (s[j] == 'S')
                    start = jd + j;
            }
            jd += n;
        }

        int k;
        if (bfs()) {
            ans = 0;
            goto L;
        }
        char ch[3];
        for (i = 0; i < m * n; ++i) {
            if (map[i] == '#' || map[i] == 'S' || map[i] == 'E') {
                continue;
            }
            ch[0] = map[i];
            map[i] = '#';

            if (bfs()) {
                ans = 1;
                goto L;
            }
            map[i] = ch[0];
        }
        for (i = 0; i < m * n; ++i) {
            if (map[i] == '#' || map[i] == 'S' || map[i] == 'E') {
                continue;
            }
            ch[0] = map[i];
            map[i] = '#';
            for (j = i + 1; j < m * n; ++j) {
                if (map[j] == '#' || map[j] == 'S' || map[j] == 'E') {
                    continue;
                }
                ch[1] = map[j];
                map[j] = '#';

                if (bfs()) {
                    ans = 2;
                    goto L;
                }
                map[j] = ch[1];
            }
            map[i] = ch[0];
        }

        for (i = 0; i < m * n; ++i) {
            if (map[i] == '#' || map[i] == 'S' || map[i] == 'E') {
                continue;
            }
            ch[0] = map[i];
            map[i] = '#';
            for (j = i + 1; j < m * n; ++j) {
                if (map[j] == '#' || map[j] == 'S' || map[j] == 'E') {
                    continue;
                }
                ch[1] = map[j];
                map[j] = '#';
                for (k = j + 1; k < m * n; ++k) {
                    if (map[k] == '#' || map[k] == 'S' || map[k] == 'E') {
                        continue;
                    }
                    ch[2] = map[k];
                    map[k] = '#';
                    if (bfs()) {
                        ans = 3;
                        goto L;
                    }
                    map[k] = ch[2];
                }
                map[j] = ch[1];
            }
            map[i] = ch[0];
        }

        ans = 4;
L:
        printf("%d\n", ans);
    }
    return 0;


}