简单BFS。
/* 2757 */
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std; #define MAXN 1005 typedef struct node_t {
int k, t;
node_t() {}
node_t(int kk, int tt) {
k = kk; t = tt;
}
friend bool operator <(const node_t &a, const node_t &b) {
return a.t > b.t;
}
} node_t; int n, m;
int bx, by, ex, ey;
char map[MAXN][MAXN];
int visit[MAXN][MAXN];
int dir[][] = {
-,, -,, ,, ,,
,, ,-, ,-, -,-
}; inline bool check(int x, int y) {
return x< || x>=n || y<= || y>=m;
} int bfs() {
int xx, yy;
int x, y, t;
int i, j, k;
node_t nd;
priority_queue<node_t> Q; memset(visit, 0x3f, sizeof(visit));
visit[bx][by] = ;
nd.t = ;
nd.k = bx*+by;
Q.push(nd); while (!Q.empty()) {
nd = Q.top();
xx = nd.k/;
yy = nd.k%;
if (xx==ex && yy==ey)
return nd.t;
Q.pop();
for (i=; i<; ++i) {
x = xx + dir[i][];
y = yy + dir[i][];
if (check(x, y))
continue;
if (map[xx][yy] == i)
t = nd.t;
else
t = nd.t + ;
if (visit[x][y] > t) {
visit[x][y] = t;
k = *x+y;
Q.push(node_t(k, t));
}
}
} return ;
} int main() {
int i, j, k;
int t; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%d%d",&n,&m) != EOF) {
for(i=; i<n; ++i) {
scanf("%s", map[i]);
for (j=; j<m; ++j)
map[i][j] -= '';
}
scanf("%d", &t);
while (t--) {
scanf("%d%d%d%d",&bx,&by,&ex,&ey);
--bx; --by; --ex; --ey;
if (bx==ex && by==ey)
k = ;
else
k = bfs();
printf("%d\n", k);
}
} return ;
}