Kvar_ispw17's blog
0%

Posted on In

题目链接：HDU 3085 Nightmare Ⅱ

题目大意

​ 给一个地图，有些地方不能走。二明和他的女朋友被两个鬼追，所以他们二人希望尽快团聚。每个单位时间，二明可以走 \(3\) 步，女朋友可以走 \(1\) 步，人类不能穿墙。每一个单位时间鬼可以分裂，并占据当前状态向外拓展 \(2\) 步的所有地点覆盖。问二人幸福美满快乐地团聚所需的最小时间。

题解

  1. 如何判断当前位置是否有鬼？

    由于鬼可以穿墙，我们发现利用两点之间的折线距离——即曼哈顿距离 \(\text{dis} = |x_1-x_2|+|y_1-y_2|\) 可以直接判断：设当前时刻为 \(t\)，如果该点到某一个鬼的位置折线距离 \(\text{dis} \leq 2t\)，说明该点被鬼的分身已经占据。

  2. 怎么在一个单位时间让两人走不同的步数？

    注意到，在传统 \(\text{bfs}\) 中，我们每次取队首，得到新的合法位置，然后就直接把新的位置放到了队尾，从而没法考虑步数的问题。 现在我们在传统 \(\text{bfs}\) 中再加入一个临时队列 \(\text{tmp}\)，并且每次取当前队列 \(q\) 得到下一步的所有位置，并把下一步的所有位置加入临时队列 \(\text{tmp}\)，以保证每次只考虑走一步，最后再 \(q = \text{tmp}\)，重复该过程 \(k\) 次，就代表一共连续考虑了 \(k\) 步。

  3. 其他小细节？

    开一个数组 \(\text{d}[4][2]\) 存坐标的变化：\(\{0,1,0,-1,1,0,-1,1\}\)，使拓展新坐标时代码简洁。 当二人存当前状态的队列均为空时退出，设一个布尔变量判断是否相遇并输出当前的时刻（由于步长相同，所以该时刻满足一定是最短时间）。 （最开始样例的第三组数据总是 \(\text{WA}\) ，结果发现一个大 \(\text{bug}\)：当前队列里的点可能在上一个点还没有鬼占据，但是这一个时刻可能已经非法了！于是我又写了一个 \(\text{check_ghost()}\) 专门判断是不是有鬼占据……）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
// #include <cstdlib>
// #include <windows.h>
using namespace std;

typedef long long ll;

const int N = 800 + 5;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for(c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int T, m, n;
char a[N][N];

struct pos {
    int x, y;
    pos() {}
    pos(int _x, int _y): x(_x), y(_y) {}
}; // 管学长说写struct更好~

int d[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
vector<pos> Z; // Ghosts !

bool check(const pos &p, int op, int t) {
    int x = p.x;
    int y = p.y;
    if(op == 0 && a[x][y] == 'M') return false;
    if(op == 1 && a[x][y] == 'G') return false;
    if(a[x][y] == 'X') return false;
    if(x < 1 || x > n || y < 1 || y > m) return false;
    for(int i = 0; i < 2; i++) {
        pos &Zp = Z[i];
        int _x = Zp.x;
        int _y = Zp.y;
        int dis = abs(x - _x) + abs(y - _y);
        if(dis <= 2 * t) return false;
    }
    return true;
}

bool check_ghost(const pos &p, int op, int t) {
    int x = p.x;
    int y = p.y;
    for(int i = 0; i < 2; i++) {
        pos &Zp = Z[i];
        int _x = Zp.x;
        int _y = Zp.y;
        int dis = abs(x - _x) + abs(y - _y);
        if(dis <= 2 * t) return false;
    }
    return true;
}

void print_map() {
    // system("cls");
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            printf("%c", a[i][j]);
        }
        puts("");
    }
    // Sleep(100);
}

bool bfs(queue<pos> &q, int op, int s, int t) {
    queue<pos> tmp;
    for(int i = 1; i <= s; i++) {
        // printf("step = %d\n", i);
        while(!q.empty()) {
            pos p = q.front();
            q.pop();
            if(!check_ghost(p, op, t)) {
                continue;
            }
            for(int j = 0; j < 4; j++) {
                pos np;
                np.x = p.x + d[j][0];
                np.y = p.y + d[j][1];
                if(check(np, op, t)) {
                    if(op == 0) {
                        if(a[np.x][np.y] == 'G') {
                            // printf("FOUND G at (%d, %d)\n", np.x, np.y);
                            return true;
                        }
                        else a[np.x][np.y] = 'M';
                    }
                    if(op == 1) {
                        if(a[np.x][np.y] == 'M') {
                            // printf("FOUND M at (%d, %d)\n", np.x, np.y);
                            return true;
                        }
                        else a[np.x][np.y] = 'G';
                    }
                    tmp.push(np);
                    // printf("\tGOT (%d, %d)\n", np.x, np.y);
                }
            }
        }
        q = tmp;
        while(!tmp.empty()) tmp.pop();
    }
    return false;
}

void init() {
    Z.clear();
    memset(a, 0, sizeof a);
}

char str[N];

int main() {
    // freopen("t5.in", "r", stdin);
    read(T);
    while(T--) {
        init();
        queue<pos> M, G;
        read(n), read(m);
        for(int i = 1; i <= n; i++) {
            scanf("%s", str + 1);
            for(int j = 1; j <= m; j++) {
                char c = str[j];
                a[i][j] = c;
                if(c == 'M') M.push(pos(i, j));
                if(c == 'G') G.push(pos(i, j));
                if(c == 'Z') Z.push_back(pos(i, j));
            }
        }
        int t = 0;
        bool f = 0;
        while(!(M.empty() && G.empty())) {
            t++;
            if(bfs(M, 0, 3, t)) { 
                // printf("M found G!\n");
                f = 1; 
                break;
            }
            if(bfs(G, 1, 1, t)) {
                // printf("G found M!\n");
                f = 1;
                break;
            }
            // printf("t = %d [%d][%d]\n", t, M.size(), G.size());
        }
        // print_map();
        printf("%d\n", f ? t : -1);
    }
    return 0;   
}