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
| #include<bits/stdc++.h>
using namespace std;
#define id(x, y, d) ((x - 1) * M + y) + N * M * (d)
const int INF = 0x3f3f3f3f;
struct Edge {
int v, w;
Edge(int v, int w): v(v), w(w) {}
};
vector<Edge> G[35 * 35 * 5];
int nx[] = {0, -1, 0, 1};
int ny[] = {-1, 0, 1, 0};
int N, M, Q;
int h[35][35];
int t[35][35];
bool vis[35][35];
void getdis(int x, int y, int px, int py) {
memset(t, 0x3f, sizeof(t));
memset(vis, 0, sizeof(vis));
if (h[x][y] == 0) return;
queue<pair<int, int> > q;
t[x][y] = 1, vis[x][y] = 1;
q.push(make_pair(x, y));
while (q.size()) {
int ux = q.front().first, uy = q.front().second;
q.pop();
for (int d = 0; d <= 3; ++d) {
int tx = ux + nx[d], ty = uy + ny[d];
if (tx < 1 || tx > N || ty < 1 || ty > M) continue;
if (tx == px && ty == py) continue;
if (h[tx][ty] == 0 || vis[tx][ty]) continue;
t[tx][ty] = t[ux][uy] + 1;
q.push(make_pair(tx, ty));
vis[tx][ty] = 1;
}
}
}
inline void AddEdge(int u, int v, int w) {
G[u].push_back(Edge(v, w));
}
bool v[35 * 35 * 5];
int d[35 * 35 * 5];
void Dijkstra(int S) {
memset(v, 0, sizeof(v));
memset(d, 0x3f, sizeof(d));
d[S] = 0;
priority_queue<pair<int, int> > q;
q.push(make_pair(0, S));
while (q.size()) {
int u = q.top().second;
q.pop();
if (v[u]) continue;
v[u] = 1;
for (vector<Edge>::iterator it = G[u].begin(); it != G[u].end(); it++) {
int v = it->v, w = it->w;
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
q.push(make_pair(-d[v], v));
}
}
}
}
int main() {
scanf("%d%d%d", &N, &M, &Q);
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
scanf("%d", &h[i][j]);
for (int x = 1; x <= N; ++x) {
for (int y = 1; y <= M; ++y) {
if (h[x][y] == 0) continue;
for (int d = 0; d <= 3; ++d) {
int tx = x + nx[d], ty = y + ny[d];
if (tx < 1 || tx > N || ty < 1 || ty > M) continue;
if (h[tx][ty] == 0) continue;
getdis(x, y, tx, ty);
for (int d2 = 0; d2 <= 3; ++d2) {
int tx2 = tx + nx[d2], ty2 = ty + ny[d2];
if (tx2 < 1 || tx2 > N || ty2 < 1 || ty2 > M) continue;
if (t[tx2][ty2] >= INF) continue;
AddEdge(id(x, y, d), id(tx, ty, d2), t[tx2][ty2]);
}
}
}
}
while (Q--) {
int ex, ey, sx, sy, tx, ty;
scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
if (sx == tx && sy == ty) {
puts("0");
continue;
}
getdis(ex, ey, sx, sy);
int ans = INF;
for (int d1 = 0; d1 <= 3; ++d1) {
int fx = sx + nx[d1], fy = sy + ny[d1];
if (fx < 1 || fx > N || fy < 1 || fy > M) continue;
if (t[fx][fy] >= INF) continue;
int cur = INF;
Dijkstra(id(sx, sy, d1));
for (int d2 = 0; d2 <= 3; ++d2)
cur = min(cur, d[id(tx, ty, d2)]);
cur += t[fx][fy] - 1;
ans = min(ans, cur);
}
if (ans >= INF) puts("-1");
else printf("%d\n", ans);
}
return 0;
}
|