题目描述
输入格式
输出格式
样例
数据范围与提示
把状态看做点，转移的代价看成边，于是就变成了最短路问题。
我们把少量的有用的状态拿出来进行连边。
$large id[i][j][k]$为空格在$large (i, j)$的k方向的状态的编号。
然后用bfs处理出[i][j][k] 到 [i][j][p] 的路径长度连边。
还有一种转移是空格和(i, j)换位置， [i][j][k] 与 [i'][j'][k^1] 连边权1的边。
每次开始的时候把空格点跑bfs，向起点的四周连边。
然后spfa跑最短路。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; inline int read() { int res=0;char ch=getchar();bool flag=0; while(!isdigit(ch)) {if(ch=='-')flag=1;ch=getchar();} while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48), ch=getchar(); return flag ? -res : res; } #define reg register int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; int n, m, q; bool mp[35][35]; int id[35][35][5], tot; int Ex, Ey, Sx, Sy, Tx, Ty; struct edge { int nxt, to, val; }ed[35*35*35*2]; int head[35*35*4], cnt; inline void add(int x, int y, int z) { if (z == 0x3f3f3f3f) return ; ed[++cnt] = (edge) {head[x], y, z}; head[x] = cnt; } struct date { int x, y, stp; }; int stp[35][35]; int dis[35*35*8]; bool vis[35][35]; bool ex[35*35*8]; inline bool ok(int x, int y) { if (!mp[x][y] and x > 0 and x <= n and y > 0 and y <= m) return 1; return 0; } inline int bfs(int sx, int sy, int tx, int ty, int fx, int fy) { if (sx == tx and sy == ty) return 0; memset(vis, 0, sizeof vis); queue <date> q; q.push((date){sx, sy, 0}); vis[sx][sy] = 1; while(!q.empty()) { int x = q.front().x, y = q.front().y, tp = q.front().stp;q.pop(); for (reg int i = 0 ; i < 4 ; i ++) { int ux = x + dx[i], uy = y + dy[i]; if (ok(ux, uy) and !vis[ux][uy]) { vis[ux][uy] = 1; if (ux == fx and uy == fy) continue; if (ux == tx and uy == ty) return tp + 1; q.push((date){ux, uy, tp + 1}); } } } return 0x3f3f3f3f; } int main() { memset(mp, 1, sizeof mp); n = read(), m = read(), q = read(); for (reg int i = 1 ; i <= n ; i ++) for (reg int j = 1 ; j <= m ; j ++) if (read()) mp[i][j] = 0;//如果不固定就是0 for (reg int i = 1 ; i <= n ; i ++) for (reg int j = 1 ; j <= m ; j ++) for (reg int k = 0 ; k < 4 ; k ++) id[i][j][k] = ++tot; for (reg int i = 1 ; i <= n ; i ++) { for (reg int j = 1 ; j <= m ; j ++) { if (mp[i][j]) continue; for (reg int k = 0 ; k < 4 ; k ++) { int tx = i + dx[k], ty = j + dy[k]; if (ok(tx, ty)) add(id[i][j][k], id[tx][ty][k^1], 1); } } } for (reg int i = 1 ; i <= n ; i ++) { for (reg int j = 1 ; j <= m ; j ++) { if (mp[i][j]) continue; for (reg int k = 0 ; k < 4 ; k ++) { int x1 = i + dx[k], y1 = j + dy[k]; if (!ok(x1, y1)) continue; for (reg int p = 0 ; p < 4 ; p ++) { int x2 = i + dx[p], y2 = j + dy[p]; if (k != p and ok(x2, y2)) { int tmp = bfs(x1, y1, x2, y2, i, j); if (tmp != 0x3f3f3f3f) add(id[i][j][k], id[i][j][p], tmp); } } } } } while(q--) { Ex = read(), Ey = read(), Sx = read(), Sy = read(), Tx = read(), Ty = read(); if (Sx == Tx and Sy == Ty) {puts("0");continue;} queue <int> q; memset(dis, 0x3f, sizeof dis); for (reg int i = 0 ; i < 4 ; i ++) { int x = Sx + dx[i], y = Sy + dy[i]; if (ok(x, y)) { dis[id[Sx][Sy][i]] = bfs(Ex, Ey, x, y, Sx, Sy); q.push(id[Sx][Sy][i]); } } while(!q.empty()) { int x = q.front();q.pop(); ex[x] = 0; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; if (dis[to] > dis[x] + ed[i].val) { dis[to] = dis[x] + ed[i].val; if (!ex[to]) ex[to] = 1, q.push(to); } } } int ans = 0x3f3f3f3f; for (reg int i = 0 ; i < 4 ; i ++) ans = min(ans, dis[id[Tx][Ty][i]]); printf("%d ", ans == 0x3f3f3f3f ? -1 : ans); } return 0; }