CF413E Maze 2D
### 线段树
题目
宽度只有\(1\)的话怎么做?
用线段树维护一下\(dis\)表示\(l-r\)区间的距离
那么宽度为\(2\)的也一样啊
就可以设四个距离
表示左上到右上,左上到右下,左下到右上,左下到右下
这样就可以查询了
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+10,inf=0x3f3f3f3f;
int n,m,tu[10][maxn];
struct tree{
int dt[5];//左上到右上 左上到右下 左下到右上 左下到右下
}tr[maxn<<2];
inline void pushup(int p){
tree ls=tr[p<<1],rt=tr[p<<1|1];
tr[p].dt[1]=min(inf,min(ls.dt[1]+rt.dt[1],ls.dt[2]+rt.dt[3])+1);
tr[p].dt[2]=min(inf,min(ls.dt[1]+rt.dt[2],ls.dt[2]+rt.dt[4])+1);
tr[p].dt[3]=min(inf,min(ls.dt[3]+rt.dt[1],ls.dt[4]+rt.dt[3])+1);
tr[p].dt[4]=min(inf,min(ls.dt[4]+rt.dt[4],ls.dt[3]+rt.dt[2])+1);
return;
}
void build(int p,int l,int r){
if(l==r){
tr[p].dt[1]=tr[p].dt[2]=tr[p].dt[3]=tr[p].dt[4]=inf;
if(tu[1][l]) tr[p].dt[1]=0;
if(tu[2][l]) tr[p].dt[4]=0;
if(tu[1][l] && tu[2][l]) tr[p].dt[2]=tr[p].dt[3]=1;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
pushup(p);
}
inline tree qry(int p,int l,int r,int x,int y){
if(x<=l && r<=y) return tr[p];
int mid=(l+r)>>1;
tree ls,rt,res;
bool fl1=0,fl2=0;
if(x<=mid) ls=qry(p<<1,l,mid,x,y),fl1=1;
if(mid<y) rt=qry(p<<1|1,mid+1,r,x,y),fl2=1;
if(fl1 && !fl2) return ls;
if(!fl1 && fl2) return rt;
res.dt[1]=min(inf,min(ls.dt[1]+rt.dt[1],ls.dt[2]+rt.dt[3])+1);
res.dt[2]=min(inf,min(ls.dt[1]+rt.dt[2],ls.dt[2]+rt.dt[4])+1);
res.dt[3]=min(inf,min(ls.dt[3]+rt.dt[1],ls.dt[4]+rt.dt[3])+1);
res.dt[4]=min(inf,min(ls.dt[4]+rt.dt[4],ls.dt[3]+rt.dt[2])+1);
return res;
}
inline int ask(int x,int y){
int a=(x-1)%n+1,b=(y-1)%n+1;
if(a>b){ swap(x,y);swap(a,b); }
tree xx=qry(1,1,n,a,b);
if(x<=n && y<=n) return xx.dt[1];
if(x<=n && y>n) return xx.dt[2];
if(x>n && y<=n) return xx.dt[3];
if(x>n && y>n) return xx.dt[4];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=2;i++){
string s;cin>>s;
for(int j=0;j<n;j++) if(s[j]=='.') tu[i][j+1]=1;
}
build(1,1,n);
while(m--){
int x,y;scanf("%d%d",&x,&y);
int ans=ask(x,y);
if(ans>=inf) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}