街机争霸

题意

在一个n * m的矩阵中，给定起点和终点，然后还有障碍，甚至还有僵尸。僵尸的活动范围由给定的方向和k决定的为一个1 * k的矩形，僵尸在这个范围上来回活动。问从起点到达终点的最短时间。

题解

按照题目意思去走就好了，重点在于怎么处理僵尸的行走问题。因为k的范围比较小，你可以开一个三维vis数组，vis[i][j][t]记录当你到达i行j列时状态为t时。那么数组的开销就是n * m * (2 * k)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2 + 7;
struct Zombie {
    int x, y, dire; // dire 0代表左  1代表右 2代表上 3代表下
}zombies[N];
struct Node {
    int x, y, d;
}q[N * N * 80];
char s[N][N];
int n, m, p, k, vis[N][N][27];
const int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
pair<int, int> calc(int p, int d) {
    if (d > k) {
        if (zombies[p].dire == 0) return make_pair(zombies[p].x, zombies[p].y - k + (d - k));
        else if (zombies[p].dire == 1) return make_pair(zombies[p].x, zombies[p].y + k - (d - k));
        else if (zombies[p].dire == 2) return make_pair(zombies[p].x - k + (d - k), zombies[p].y);
        else return make_pair(zombies[p].x + k - (d - k), zombies[p].y);
    }
    else {
        if (zombies[p].dire == 0) return make_pair(zombies[p].x, zombies[p].y - d);
        else if (zombies[p].dire == 1) return make_pair(zombies[p].x, zombies[p].y + d);
        else if (zombies[p].dire == 2) return make_pair(zombies[p].x - d, zombies[p].y);
        else return make_pair(zombies[p].x + d, zombies[p].y);
    }
}
bool check(int x, int y, int s) {
    bool ret = true;
    int re = s % (2 * k);
    for (int i = 1; i <= p; i++) {
        pair<int, int> pos = calc(i, re);
        if (pos.first == x && pos.second == y) ret = false;
    }
    return ret;
}
int bfs() {
    int l = 0, r = 0, ex = 0, ey = 0, num = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'L') q[r++] = Node{i, j, 0}, vis[i][j][0] = 1;
            if (s[i][j] == 'A') ex = i, ey = j;
        }
    }
    while (l < r) {
        Node now = q[l++];
        if (now.x == ex && now.y == ey) return now.d;
        for (int i = 0; i < 4; i++) {
            int dx = direction[i][0] + now.x;
            int dy = direction[i][1] + now.y;
            if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && s[dx][dy] != '&' && !vis[dx][dy][(now.d + 1) % (2 * k)] && check(dx, dy, now.d + 1)) {
                q[r++] = Node{dx, dy, now.d + 1};
                vis[dx][dy][(now.d + 1) % (2 * k)] = 1;
            }
        }
    }
    return -1;
}
void solve() {
    char dr[N];
    scanf("%d%d%d%d", &n, &m, &p, &k); k -= 1;
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
    }
    for (int i = 1; i <= p; i++) {
        scanf("%d%d%s", &zombies[i].x, &zombies[i].y, dr);
        if (dr[0] == 'R') zombies[i].dire = 1; 
        else if (dr[0] == 'L') zombies[i].dire = 0;
        else if (dr[0] == 'U') zombies[i].dire = 2;
        else zombies[i].dire = 3;
    }
    int ret = bfs();
    if (ret == -1) printf("Oh no\n");
    else printf("%d\n", ret);
}
int main() {
    solve();
    return 0;
}