Description
Luogu1979
给定一个棋盘，有一个格子是空的，其余格子都有棋子，其中一些棋子是固定的，现在要求出将一个棋子S移动到目标位置的步数。
Solution
这个题的暴力还是很好打的，一个标准的bfs（状态是空白格的位置和S的位置）就可以拿到70分，不过要注意如果是hash判重的话，不要hash碰撞啊。
然后就是一个很巧妙的转化了：注意到bfs的过程实际上是求出了从初状态到末状态在状态转移图上的最短路，可以转化成最短路问题。但是，由于我们的状态是(O(n^2m^2))的，无法建出状态转移图。所以考虑精简状态，注意到只有S和空白格相邻的状态才是对S的移动有用的，那么可以定义状态为(Sta_{i,j,k})，表示S在((i,j))这个位置，空格在S的(k)方向（上下左右分别对应0123）。这样状态数就降下来了，并且末状态就是(Sta_{T_x, T_y, k})。我们再来思考转移，一个比较高效的转移方法是从(Sta_{i,j,k})转移到空格在((i,j))处，S在((i,j))的四个相邻位置上，这样转移也是比较优的：计算量不大（bfs计算出空格从(k)这个方向移到另一个方向的代价，然后+1就是这个转移的代价），而且转移数比较少。还有一个问题，那就是初始的时候空格不一定在S旁边，那就bfs算出把空格移到S旁边的代价，连一条边就行。最后，在状态转移图上跑最短路就行了。
Code
满分代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define REP(i, j, k) for (int i = j; i <= k; ++i)
const int N = 35;
const int INF = 0x3f3f3f3f;
const int EM = N * N * 4 * 4;
const int VN = N * N * 4;
const int MOV[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct Node {
int x, y;
Node (int a=0, int b=0) : x(a), y(b) {}
};
int tot; // 状态数
int s[N][N], Sta[N][N][4], step[N][N], vis[N][N], Len[N][N][4][4];
// 原图， 状态， BFS辅助数组*2， 转移代价
int hd[VN], nxt[EM], to[EM], w[EM], cnt; // 邻接表存边
int n, m, q, ex, ey, sx, sy, tx, ty; // 同原题
int Vis[VN], Dis[VN]; // 跑最短路用的
int BFS(int sx, int sy, int tx, int ty) { // 计算把空格从(sx, sy)移到(tx, ty)代价。
if (sx == tx && sy == ty) return 0; // mark : was `sx == sy && tx == ty`
memset(step, 0, sizeof step);
memset(vis, 0, sizeof vis);
std::queue<Node> que;
que.push(Node(sx, sy));
while (!que.empty()) {
Node tmp = que.front(); que.pop();
if (vis[tmp.x][tmp.y]) continue;
vis[tmp.x][tmp.y] = 1;
if (tmp.x == tx && tmp.y == ty) return step[tmp.x][tmp.y];
REP(k, 0, 3) {
if (s[tmp.x+MOV[k][0]][tmp.y+MOV[k][1]]
&& !vis[tmp.x+MOV[k][0]][tmp.y+MOV[k][1]]) {
que.push(Node(tmp.x+MOV[k][0], tmp.y+MOV[k][1]));
step[tmp.x+MOV[k][0]][tmp.y+MOV[k][1]] = step[tmp.x][tmp.y] + 1;
}
}
}
return INF;
}
inline void adde(int x, int y, int z) {
cnt++;
to[cnt] = y;
w[cnt] = z;
nxt[cnt] = hd[x];
hd[x] = cnt;
}
struct node {
int p, d;
node (int a=0, int b=0) : p(a), d(b) {}
bool operator< (const node &x) const { return d > x.d; }
};
std::priority_queue<node> pq;
inline int dij(int s, int t) {
memset(Vis, 0, sizeof Vis);
memset(Dis, 0x3f, sizeof Dis);
pq.push(node(s, Dis[s] = 0));
while (!pq.empty()) {
node x = pq.top(); pq.pop();
if (Vis[x.p]) continue;
Vis[x.p] = 1;
for (int i = hd[x.p]; i; i = nxt[i]) if (!Vis[to[i]]) {
if (Dis[to[i]] > Dis[x.p] + w[i]) {
pq.push(node(to[i], Dis[to[i]] = Dis[x.p] + w[i]));
}
}
}
return Dis[t] == INF ? -1 : Dis[t];
}
int main() {
// 输入
scanf("%d%d%d", &n, &m, &q);
REP(i, 1, n) REP(j, 1, m) scanf("%d", &s[i][j]);
// 建立状态转移图
// 计算状态标号
REP(i, 1, n) REP(j, 1, m) if (s[i][j]) {
REP(k, 0, 3) if (s[i + MOV[k][0]][j + MOV[k][1]]) {
Sta[i][j][k] = ++tot;
}
}
// 计算转移代价
memset(Len, 0x3f, sizeof Len);
REP(i, 1, n) REP(j, 1, m) if (s[i][j]) {
s[i][j] = 0;
REP(k, 0, 3) if (Sta[i][j][k]) {
REP(h, 0, 3) if (Sta[i][j][h]) {
Len[i][j][k][h] = BFS(i+MOV[k][0], j+MOV[k][1], i+MOV[h][0], j+MOV[h][1]) + 1;
}
}
s[i][j] = 1;
}
// 建图
REP(i, 1, n) REP(j, 1, m) if (s[i][j]) {
REP(k, 0, 3) if (Sta[i][j][k]) {
REP(h, 0, 3) if (Sta[i][j][h]) {
if (Len[i][j][k][h] <= INF) {
adde(Sta[i][j][k], Sta[i+MOV[h][0]][j+MOV[h][1]][h^1], Len[i][j][k][h]);
}
}
}
}
// 处理询问
while (q--) {
scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
if (sx == tx && sy == ty) {
puts("0");
continue;
}
int S = ++tot, T = ++tot;
s[sx][sy] = 0;
REP(k, 0, 3) if (Sta[sx][sy][k]) {
int len = BFS(ex, ey, sx+MOV[k][0], sy+MOV[k][1]);
if (len < INF) adde(S, Sta[sx][sy][k], len);
}
REP(k, 0, 3) if (Sta[tx][ty][k]) {
adde(Sta[tx][ty][k], T, 0);
}
s[sx][sy] = 1;
printf("%d
", dij(S, T));
}
return 0;
}
70分暴力：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int N = 35;
const int M = 1e6;
const int MOV[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int s[N][N];
int tx, ty, n, m, q, HA;
struct State {
int sx, sy, ex, ey, ha;
State(int a=0, int b=0, int c=0, int d=0) : sx(a), sy(b), ex(c), ey(d), ha(0) {}
int hash() { // 注意不要哈希碰撞（其实可以不哈希，用四维数组判重）
if (ha) return ha;
ha = ((sx * HA + sy) * HA + ex) * HA + ey;
return ha;
}
};
std::queue<State> que;
int vis[M], step[M];
int main() {
scanf("%d%d%d", &n, &m, &q);
HA = std::max(n, m) + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &s[i][j]);
}
}
while (q--) {
memset(vis, 0, sizeof vis);
memset(step, 0, sizeof step);
while (!que.empty()) que.pop();
State sta;
scanf("%d%d%d%d%d%d", &sta.ex, &sta.ey, &sta.sx, &sta.sy, &tx, &ty);
que.push(sta);
int tot = 0, ans = -1;
while (!que.empty()) {
tot++;
State tmp = que.front(); que.pop();
if (vis[tmp.hash()]) continue;
if (tmp.sx == tx && tmp.sy == ty) {
ans = step[tmp.hash()];
break;
}
vis[tmp.hash()] = 1;
for (int i = 0; i < 4; ++i) {
if (!s[tmp.ex + MOV[i][0]][tmp.ey + MOV[i][1]]) continue;
if (tmp.ex + MOV[i][0] == tmp.sx && tmp.ey + MOV[i][1] == tmp.sy)
State sta = State(tmp.ex, tmp.ey, tmp.sx, tmp.sy);
else
State sta = State(tmp.sx, tmp.sy, tmp.ex+MOV[i][0], tmp.ey+MOV[i][1]);
if (!vis[sta.hash()]) {
que.push(sta);
step[sta.hash()] = step[tmp.hash()] + 1;
}
}
}
printf("%d
", ans);
}
return 0;
}