P1979华容道

这是NOIP2013的Day2T2
考虑暴力做法,则是对于每个询问bfs,这样很明显会超时
如何优化呢
考虑有用的状态
只有当空白块到了指定块的四周,它才可以带着指定块移动
从这一个状态可以转移到四种状态,分别是空白块到了指定块的其他三个方向以及空白块与指定块交换位置
这样就是一个最短路问题,可以用spfa解决了
至于空白块到其他三个方向的距离,可以向bfs预处理出来,直接与处理出每个块每个方向上有空白块的情况然后连边
对于每次询问进行spfa
还有就是开始时空白块不一定在指定块周围
这时候就要bfs处理出空白块到指定块周围所需的步数
最后统计时取空白块在目标块的四个方向时距离最短的就是了
Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define LL long long
#define P pair<int, int>
using namespace std;
template <typename T>
inline void read(T &t)
{
int f = 0, c = getchar();
t = 0;
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
t = t * 10 + c - 48, c = getchar();
if (f)
t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &... args)
{
read(t);
read(args...);
}
const int maxn = 32;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, q;
int predis[maxn][maxn];
int dis[maxn * maxn * 5];
int vis[maxn * maxn * 5];
int a[maxn][maxn];
struct Edge
{
int from, to, weight;
Edge(int u, int v, int w) : from(u), to(v), weight(w) {}
};
struct Point
{
int x, y;
Point(int x,int y):x(x),y(y){}
};
vector<Edge> G[maxn * maxn * 5];
void ae(int u, int v, int w)
{
G[u].push_back(Edge(u, v, w));
}
int num(int x, int y)
{
y--;
return (x - 1) * m + y << 2;//将xy坐标表示成一个整数
}
void bfs(int ex, int ey, int px, int py, int d)//空白块为ex,ey,指定块为px,py,空白块在指定块的d方向上
{
memset(predis, -1, sizeof(predis));
predis[px][py] = 1;//由于指定块不能动所以距离直接赋1防止bfs时被访问到
predis[ex][ey] = 0;
queue<Point> q;
q.push(Point(ex, ey));
while (!q.empty())
{
Point cur = q.front();
q.pop();
int cx = cur.x, cy = cur.y;
for (int i = 0; i < 4; i++)
{
int nx = cx + dx[i];
int ny = cy + dy[i];
if (a[nx][ny] && predis[nx][ny] == -1)
{
predis[nx][ny] = predis[cx][cy] + 1;
q.push(Point(nx, ny));
}
}
}
if (d == 233)//用于在做spfa前的dfs,不用加边
return;
int tmp = num(px, py);
for (int i = 0; i < 4; i++)
{
int nx = px + dx[i];
int ny = py + dy[i];
if (predis[nx][ny] > 0)
{
ae(tmp + d, tmp + i, predis[nx][ny]);//空白块移动到指定块的其他三个方向的距离,这里并没有判产生子环,但其实没有关系
}
}
ae(tmp + d, num(ex, ey) + (d + 2) % 4, 1);//指定块与空白块交换,用了一点骚操作
}
void spfa(int sx, int sy)//简单的spfa,从sx,sy出发
{
memset(dis, -1, sizeof(dis));
queue<int> q;
for (int i = 0; i < 4; i++)
{
int nx = sx + dx[i], ny = sy + dy[i];
if (predis[nx][ny] != -1)
{
int tmp = num(sx, sy) + i;
dis[tmp] = predis[nx][ny];
q.push(tmp);
}
}
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = 0; i < G[u].size(); i++)
{
Edge &e = G[u][i];
if (dis[e.to] == -1 || dis[e.to] > dis[u] + e.weight)
{
dis[e.to] = dis[u] + e.weight;
if (!vis[e.to])
{
vis[e.to] = true;
q.push(e.to);
}
}
}
}
}
int main()
{
read(n, m, q);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
read(a[i][j]);
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j])
{
if (a[i - 1][j])
bfs(i - 1, j, i, j, 0);
if (a[i][j + 1])
bfs(i, j + 1, i, j, 1);
if (a[i + 1][j])
bfs(i + 1, j, i, j, 2);
if (a[i][j - 1])
bfs(i, j - 1, i, j, 3);
//预处理连边
}
}
}
int ex,ey,sx,sy,tx,ty,ans;
while(q--){
read(ex, ey, sx, sy, tx, ty);
if(sx==tx && sy==ty){
puts("0");
continue;
}
bfs(ex, ey, sx, sy, 233);//先跑spfa求出空白块到指定块四周的距离
spfa(sx,sy);
ans = INT_MAX;
int tmp = num(tx, ty);
for(int i=0;i<4;i++){
if(dis[tmp+i]!=-1){
ans = min(ans, dis[tmp + i]);//枚举到目标块的四个方向取最小
}
}
if(ans==INT_MAX)
puts("-1");
else
printf("%d\n", ans);
}
}

说在后面
这题真难打