2020牛客寒假算法基础集训营5.G题(BFS)
街机争霸
https://ac.nowcoder.com/acm/contest/3006/G
G.街机争霸
题意:中文题面,直接看题目。。。
题解:因为有僵尸的限制,在传统bfs二维坐标的基础上又增加了时间。具体参考官方题解。很好的题目,学习了。
#include <bits/stdc++.h> using namespace std; const int maxn = 505; int n, m, p, k; int dstx, dsty; char mp[maxn][maxn]; int zmb[maxn][maxn][20]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dz[2] = {-1, 1}; int vis[maxn][maxn][20][2]; struct node { int x, y, z, ud; }; queue<node> q; void init() { cin >> n >> m >> p >> k; memset(vis, -1, sizeof(vis)); for (int i = 0; i < n; i++) { scanf("%s", mp[i]); for (int j = 0; j < m; j++) { if (mp[i][j] == 'A') dstx = i, dsty = j; else if (mp[i][j] == 'L') { q.push(node{i, j, 0, 0}); vis[i][j][0][0] = 0; } } } for (int i = 0; i < p; i++) { int x, y; scanf("%d%d", &x, &y); x--, y--; zmb[x][y][0] = 1; int dst; char cmd[10]; scanf("%s", cmd); if (cmd[0] == 'U') dst = 0; else if (cmd[0] == 'D') dst = 1; else if (cmd[0] == 'L') dst = 2; else if (cmd[0] == 'R') dst = 3; for (int j = 1; j < k; j++) { x = x + dx[dst]; y = y + dy[dst]; zmb[x][y][j] = 1; } } } bool check(int x, int y, int z) { if (x < 0 || x >= n) return 0; if (y < 0 || y >= m) return 0; if (mp[x][y] == '&') return 0; if (zmb[x][y][z]) return 0; return 1; } void solve() { int ans = -1; while (!q.empty()) { node tmp = q.front(); q.pop(); int x = tmp.x, y = tmp.y, z = tmp.z; if (x == dstx && y == dsty) { ans = vis[x][y][z][tmp.ud]; break; } int dst = tmp.ud; if (z == 0 || z == k - 1) dst ^= 1; for (int i = 0; i < 4; i++) { int tx = x + dx[i]; int ty = y + dy[i]; int tz = z + dz[dst]; if (check(tx, ty, tz) && vis[tx][ty][tz][dst] == -1) { vis[tx][ty][tz][dst] = vis[x][y][z][tmp.ud] + 1; q.push(node{tx, ty, tz, dst}); } } } if (ans == -1) puts("Oh no"); else printf("%d\n", ans); } int main() { init(); solve(); return 0; }