题意
在一个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;
}