然后一遍dfs 求出每個(gè)點(diǎn)到它的lca的轉(zhuǎn)彎數(shù) 最后還要判定兩個(gè)點(diǎn)在lca處是否還要一個(gè)轉(zhuǎn)彎
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
#define LL long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const int N=100005;
int head[N],I;
struct node
{
int j,next;
int k;
}edge[N*10];
int X[]={0,0,-1,1};
int Y[]={-1,1,0,0};
int K[]={1,1,2,2};
char grap[N];
bool visited[N];
int q1[N],q2[N],lca[N],d[N],prek[N],tok[N],k1[N],k2[N],ans[N];
int f[N];
vector<int>vt[N];
queue<int>qt;
int n,m;
void add(int i,int j,int k)
{
edge[I].j=j;
edge[I].k=k;
edge[I].next=head[i];
head[i]=I++;
}
void bfs(int s)
{
memset(visited,false,sizeof(visited));
visited[s]=true;
qt.push(s);
while(!qt.empty())
{
int x=qt.front();
qt.pop();
for(int i=0;i<4;++i)
{
int l1=x/m+X[i];
int l2=x%m+Y[i];
int st=x,nd=l1*m+l2;
while(l1>=0&&l1<n&&l2>=0&&l2<m&&grap[nd]=='#'&&!visited[nd])
{
visited[nd]=true;
qt.push(nd);
add(st,nd,K[i]);
st=nd;
l1=l1+X[i];
l2=l2+Y[i];
nd=l1*m+l2;
}
}
}
}
int fx(int x)
{
if(f[x]!=x)
f[x]=fx(f[x]);
return f[x];
}
void findLca(int x)
{
for(unsigned int i=0;i<vt[x].size();++i)
{
int l=vt[x][i];
if(q1[l]==x)
{
if(f[q2[l]]!=-1)
lca[l]=fx(q2[l]);
}else
{
if(f[q1[l]]!=-1)
lca[l]=fx(q1[l]);
}
}
}
void dfsLca(int x,int pre)
{
f[x]=x;
findLca(x);
for(int t=head[x];t!=-1;t=edge[t].next)
{
int j=edge[t].j;
dfsLca(j,x);
}
f[x]=pre;
}
void F(int x)
{
for(unsigned int i=0;i<vt[x].size();++i)
{
int l=vt[x][i];
int y=lca[l];
if(x==q1[l])
k1[l]=tok[y];
else
k2[l]=tok[y];
ans[l]+=(d[x]-d[y]);
if((prek[y]&tok[y])==0)
--ans[l];
}
}
void dfs(int x,int dt,int kt)
{
d[x]=dt;
prek[x]=kt;
tok[x]=3;
F(x);
for(int t=head[x];t!=-1;t=edge[t].next)
{
int j=edge[t].j;
tok[x]=edge[t].k;
if((prek[x]&tok[x])==0)
dfs(j,dt+1,edge[t].k);
else
dfs(j,dt,edge[t].k);
}
}
int main()
{
//freopen("data.in","r",stdin);
cin>>n>>m;
int s=-1;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
{
cin>>grap[i*m+j];
if(s==-1&&grap[i*m+j]=='#')
s=i*m+j;
}
memset(head,-1,sizeof(head));
I=0;
bfs(s);
int q;
cin>>q;
for(int i=0;i<q;++i)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
--x1;--y1;--x2;--y2;
q1[i]=x1*m+y1;
q2[i]=x2*m+y2;
if(q1[i]!=q2[i])
vt[q1[i]].push_back(i);
vt[q2[i]].push_back(i);
}
memset(f,-1,sizeof(f));
dfsLca(s,s);
for(int i=0;i<n*m;++i)
vt[i].clear();
for(int i=0;i<q;++i)
if(q1[i]!=q2[i])
{vt[q1[i]].push_back(i);vt[q2[i]].push_back(i);}
memset(ans,0,sizeof(ans));
dfs(s,0,3);
for(int i=0;i<q;++i)
{
if(q1[i]==q2[i])
{cout<<"0"<<endl;continue;}
if((k1[i]&k2[i])==0)
++ans[i];
cout<<ans[i]<<endl;
}
return 0;
}