传送门：https://vijos.org/p/1983
（其实noip的题各个oj都会有的，就不贴其它传送门了）
这道题真的是，怎么说，我都不知道怎么评价了= =。果然数据量小的题怎么暴力都可以过。。。当然我没说这一题要用最最暴力的bfs。
首先这一题的特点是给定一个图，之后有q（q <= 500）个询问，这很显然就是暗示我们要预处理。那么预处理什么呢？首先观察这一题，若你想让目标棋子移动到指定的位置，一定是分以下几步（注意移动棋子等价于移动空白格子）：
1) 先把空白格子移动到目标棋子的四联通块上。
2) 这样，目标棋子就可以与空白格子交换位置以实现一次移动，交换完后，空白格子仍旧在目标棋子的四联通块上
3) 再让空白格子移动到目标棋子的四联通块的另外一个块上（很显然要“另外一个”，不然不就回去了嘛），然后goto step2
我们可以定义一种状态(x, y, k)，表示目标棋子在(x, y)上，空白格子在其k方向上。所以此题的关键就是要预处理出一个go[i][j][k][p]数组，来表示目标棋子在(x, y)上，空白格子由目标棋子的k方向移动到p方向所需的最小步数，这个用bfs来处理就ok啦！剩下就是最短路了。
#include <cstdio>
#include <cstring>
#include <queue>
const int dirx[4] = {0, 1, 0, -1}, diry[4] = {1, 0, -1, 0};
const int other[4] = {2, 3, 0, 1};
int n, m, q, mp[35][35], ex, ey, sx, sy, tx, ty;
int go[35][35][4][4], head_, tail, stp[35][35], d[35][35][4];
bool book[35][35][4];
struct st1 {
int x, y;
} que[920], h;
struct st2 {
int x, y, k, d;
bool operator<(const st2 & rhs) const {
return d > rhs.d;
}
};
inline void bfs1(int x, int y, int kk) {
memset(que, 0, sizeof que);
memset(stp, 0x3c, sizeof stp);
head_ = tail = 0;
que[tail++] = (st1){x + dirx[kk], y + diry[kk]};
stp[x + dirx[kk]][y + diry[kk]] = 0;
int xx, yy;
while (head_ != tail) {
h = que[head_++];
for (int k = 0; k < 4; ++k) {
xx = h.x + dirx[k];
yy = h.y + diry[k];
if (mp[xx][yy] && stp[xx][yy] == 0x3c3c3c3c) {
stp[xx][yy] = stp[h.x][h.y] + 1;
que[tail++] = (st1){xx, yy};
}
}
}
go[x][y][kk][0] = stp[x][y + 1];
go[x][y][kk][1] = stp[x + 1][y];
go[x][y][kk][2] = stp[x][y - 1];
go[x][y][kk][3] = stp[x - 1][y];
}
inline void bfs2(int x, int y) {
memset(que, 0, sizeof que);
memset(stp, 0x3c, sizeof stp);
head_ = tail = 0;
que[tail++] = (st1){x, y};
stp[x][y] = 0;
int xx, yy;
while (head_ != tail) {
h = que[head_++];
for (int k = 0; k < 4; ++k) {
xx = h.x + dirx[k];
yy = h.y + diry[k];
if (mp[xx][yy] && stp[xx][yy] == 0x3c3c3c3c) {
stp[xx][yy] = stp[h.x][h.y] + 1;
que[tail++] = (st1){xx, yy};
}
}
}
}
int main(void) {
//freopen("in.txt", "r", stdin);
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &mp[i][j]);
}
}
memset(go, -1, sizeof go);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!mp[i][j]) {
continue;
}
mp[i][j] = 0;
for (int k = 0; k < 4; ++k) {
if (mp[i + dirx[k]][j + diry[k]]) {
bfs1(i, j, k);
}
}
mp[i][j] = 1;
}
}
while (q--) {
scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
if (sx == tx && sy == ty) {
puts("0");
continue;
}
mp[sx][sy] = 0;
bfs2(ex, ey);
mp[sx][sy] = 1;
memset(d, 0x3c, sizeof d);
memset(book, 0, sizeof book);
std::priority_queue<st2> hp;
if (stp[sx][sy + 1] < 0x3c3c3c3c) {
hp.push((st2){sx, sy, 0, stp[sx][sy + 1]});
}
if (stp[sx + 1][sy] < 0x3c3c3c3c) {
hp.push((st2){sx, sy, 1, stp[sx + 1][sy]});
}
if (stp[sx][sy - 1] < 0x3c3c3c3c) {
hp.push((st2){sx, sy, 2, stp[sx][sy - 1]});
}
if (stp[sx - 1][sy] < 0x3c3c3c3c) {
hp.push((st2){sx, sy, 3, stp[sx - 1][sy]});
}
d[sx][sy][0] = stp[sx][sy + 1];
d[sx][sy][1] = stp[sx + 1][sy];
d[sx][sy][2] = stp[sx][sy - 1];
d[sx][sy][3] = stp[sx - 1][sy];
st2 k;
int xx, yy;
while (!hp.empty()) {
k = hp.top();
hp.pop();
while (!hp.empty() && book[k.x][k.y][k.k]) {
k = hp.top();
hp.pop();
}
if (k.x == tx && k.y == ty) {
printf("%d
", k.d);
goto spe;
}
book[k.x][k.y][k.k] = true;
xx = k.x + dirx[k.k];
yy = k.y + diry[k.k];
if (d[xx][yy][other[k.k]] > k.d + 1) {
d[xx][yy][other[k.k]] = k.d + 1;
hp.push((st2){xx, yy, other[k.k], k.d + 1});
}
for (int kk = 0; kk < 4; ++kk) {
if (d[k.x][k.y][kk] > k.d + go[k.x][k.y][k.k][kk]) {
d[k.x][k.y][kk] = k.d + go[k.x][k.y][k.k][kk];
hp.push((st2){k.x, k.y, kk, d[k.x][k.y][kk]});
}
}
}
puts("-1");
spe:;
}
return 0;
}
注意输入数据的(sx, sy)有可能与(tx, ty)相等。