NOIP2013提高组.华容道

题目

509. 华容道

算法标签: 搜索, $bfs$, $spfa$

思路

不难发现, 在人移动的过程中, 箱子是不动的, 从当前位置到下一个箱子旁边的位置不会移动箱子, 可以预处理出人在每个位置到其他位置的距离预处理, 从某一个状态出发, 走到另一个状态的最短路使用$spfa$算法, 一般来说时间复杂度$O(m)$, 极端情况下时间复杂度$O(nm)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;
const int N = 35, M = 3610, K = M * 4, INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int n, m, q, g[N][N];
vector<PII> head[M];
int d1[N][N], d2[M];
bool vis[M];void add(int u, int v, int w) {head[u].push_back({v, w});
}int get(int x, int y, int z) {return ((x - 1) * m + y - 1) * 4 + z;
}void bfs(int px, int py, int bx, int by, int dir) {queue<PII> q;memset(d1, 0x3f, sizeof d1);d1[px][py] = d1[bx][by] = 0;q.push({px, py});while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (g[x][y] && d1[x][y] + 1 < d1[nx][ny]) {d1[nx][ny] = d1[x][y] + 1;q.push({nx, ny});}}}if (dir == -1) return;int u = get(bx, by, dir);for (int i = 0; i < 4; ++i) {if (i == dir) continue;int nx = bx + dx[i], ny = by + dy[i];if (d1[nx][ny] < INF) {add(u, get(bx, by, i), d1[nx][ny]);}}// 搬运到对立面的箱需要1的花费add(u, get(px, py, dir ^ 2), 1);
}int spfa(int sx, int sy, int tx, int ty) {queue<int> q;memset(d2, 0x3f, sizeof d2);for (int i = 0; i < 4; ++i) {int nx = sx + dx[i], ny = sy + dy[i];if (d1[nx][ny] < INF) {int u = get(sx, sy, i);d2[u] = d1[nx][ny];q.push(u);vis[u] = true;}}while (!q.empty()) {auto u = q.front();q.pop();vis[u] = false;for (auto [v, w] : head[u]) {if (d2[u] + w < d2[v]) {d2[v] = d2[u] + w;if (!vis[v]) {q.push(v);vis[v] = true;}}}}int ans = INF;for (int i = 0; i < 4; ++i) {ans = min(ans, d2[get(tx, ty, i)]);}if (ans == INF) ans = -1;return ans;
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> g[i][j];}}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (g[i][j]) {// 枚举人的位置for (int k = 0; k < 4; ++k) {int nx = i + dx[k], ny = j + dy[k];if (g[nx][ny]) bfs(nx, ny, i, j, k);}}}}while (q--) {int ex, ey, sx, sy, tx, ty;cin >> ex >> ey >> sx >> sy >> tx >> ty;if (sx == tx && sy == ty) cout << 0 << "\n";else {// 现将人移动到箱子周围bfs(ex, ey, sx, sy, -1);// 再从箱子周围的状态转移到最终状态int ans = spfa(sx, sy, tx, ty);cout << ans << "\n";}}return 0;
}