BZOJ4437 : [Cerc2015]Looping Labyrinth

从$(0,0)$开始BFS$2\times10^6$步，那么迷宫的形状有三种：

1.走不完$2\times10^6$步，直接判定即可。

2.可以走到$(n,0)$以及$(0,m)$，那么直接把询问点平移到一开始的小迷宫里即可。

3.可以沿着$(dx,dy)$这个向量达到某些左上角，那么先三分沿向量走的步数，把询问点平移到最近距离之后再判定。

#include<cstdio>

typedef long long ll;

const int N=105,M=2000010,U=(1<<24)-1;

int n,m,_,flag,dx,dy,i,j,x,y,h=1,t,q[M][2];char a[N][N];

struct E{int x,y;E*nxt;}*g[U+1],pool[M],*cur=pool,*p;

inline void read(int&a){

  char c;bool f=0;a=0;

  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));

  if(c!='-')a=c-'0';else f=1;

  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';

  if(f)a=-a;

}

inline void ins(int x,int y){

  int u=((x<<9)^y)&U;

  p=cur++;p->x=x;p->y=y;p->nxt=g[u];g[u]=p;

}

inline bool ask(int x,int y){

  for(p=g[((x<<9)^y)&U];p;p=p->nxt)if(p->x==x&&p->y==y)return 1;

  return 0;

}

inline int pos(int x,int n){return (x%n+n)%n;}

inline void ext(int x,int y){

  if(t==M-1)return;

  if(!a[pos(x,n)][pos(y,m)])return;

  if(ask(x,y))return;

  q[++t][0]=x;q[t][1]=y;ins(x,y);

}

inline ll abs(ll x){return x>0?x:-x;}

inline ll dis(int x,int y,ll k){return abs(k*dx+x)+abs(k*dy+y);}

inline bool query(int x,int y){

  if(t<M-1)return ask(x,y);

  if(flag)return ask(pos(x,n),pos(y,m));

  ll l=-1000000000,r=1000000000;

  while(l+5<r){

    ll len=(r-l)/3,m1=l+len,m2=r-len;

    if(dis(x,y,m1)<dis(x,y,m2))r=m2;else l=m1;

  }

  for(;l<=r;l++)if(dis(x,y,l)<=M)if(ask(l*dx+x,l*dy+y))return 1;

  return 0;

}

int main(){

  read(n),read(m);

  for(i=0;i<n;i++)for(scanf("%s",a[i]),j=0;j<m;j++)a[i][j]=a[i][j]=='.';

  ext(0,0);

  while(h<=t){

    x=q[h][0];y=q[h++][1];

    ext(x-1,y);

    ext(x+1,y);

    ext(x,y-1);

    ext(x,y+1);

  }

  if(t==M-1){

    if(ask(n,0)&&ask(0,m))flag=1;else for(i=2;i<=t;i++){

      x=q[i][0],y=q[i][1];

      if(x%n||y%m)continue;

      dx=x,dy=y;

      break;

    }

  }

  read(_);

  while(_--)read(x),read(y),puts(query(x,y)?"yes":"no");

  return 0;

}

巴特西

BZOJ4437 : [Cerc2015]Looping Labyrinth

最新文章

热门文章