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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=255,maxm=2010;
int n,m,Q,tot,a[maxn][maxn],t[maxn][maxn][4];
unsigned dis[maxm][maxm];
vector<int> to[maxm][4];
inline void addedge(int a,int b,int c){to[a][c].push_back(b);}
inline void work(){
n=read(),m=read(),Q=read();
while(m--) a[read()][read()]=-1;
for(int i=1;i<=n;a[0][i]=a[i][0]=a[n+1][i]=a[i][n+1]=-1,i++) for(int j=1;j<=n;j++)
if(!a[i][j] and (a[i-1][j]==-1 or a[i+1][j]==-1 or a[i][j-1]==-1 or a[i][j+1]==-1))
a[i][j]=++tot;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) t[i][j][0]=a[i][j-1]==-1?a[i][j]:t[i][j-1][0],t[i][j][1]=a[i-1][j]==-1?a[i][j]:t[i-1][j][1];
for(int i=n;i;i--) for(int j=n;j;j--) t[i][j][2]=a[i][j+1]==-1?a[i][j]:t[i][j+1][2],t[i][j][3]=a[i+1][j]==-1?a[i][j]:t[i+1][j][3];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]>0) for(int k=0;k<4;k++) addedge(t[i][j][k],a[i][j],k);
static pair<int,int> q[maxm*maxm];
int hd=0,tl=0;
memset(dis,-1,sizeof dis);
for(int i=1;i<=tot;i++) q[++tl]=make_pair(i,i),dis[i][i]=1;
while(hd<tl){
pair<int,int> x=q[++hd];
for(int i=0;i<4;i++) for(auto u:to[x.first][i]) for(auto v:to[x.second][i]) if(dis[u][v]==-1) dis[u][v]=dis[x.first][x.second]+1,q[++tl]=make_pair(u,v);
}
while(Q--){
int x1=read(),y1=read(),x2=read(),y2=read();
if(x1==x2 and y1==y2) puts("0");
else printf("%d\n",min({dis[t[x1][y1][0]][t[x2][y2][0]],dis[t[x1][y1][1]][t[x2][y2][1]],dis[t[x1][y1][2]][t[x2][y2][2]],dis[t[x1][y1][3]][t[x2][y2][3]]}));
}
}
}
signed main(){
star::work();
return 0;
}
|
