三种情况分别对应
bfs提前结束 (n,0) 且 (0,m) 都可达存在 (kn,km) 可达这题TM卡常啊
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef pair<int,int> abcd; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } inline void read(char *s){ char c=nc(); int len=-1; for (;!(c=='.' || c=='#');c=nc()); for (;c=='.' || c=='#';s[++len]=c,c=nc()); s[++len]=0; } int n,m; char Map[105][105]; const int M=2000000; const int P=(1<<24)-1; int hx[M+5],hy[M+5],next[M+5]; int inum,head[P+1]; inline void add(int x,int y){ int p=++inum; hx[p]=x; hy[p]=y; next[p]=head[((x<<9)^y)&P]; head[((x<<9)^y)&P]=p; } inline int ask(int x,int y){ for (int p=head[((x<<9)^y)&P];p;p=next[p]) if (hx[p]==x && hy[p]==y) return 1; return 0; } const int _dx[]={0,0,1,-1}; const int _dy[]={1,-1,0,0}; int l,r; int Qx[M],Qy[M]; const int LIM=10000; int cnt; inline void bfs(){ l=r=-1; Qx[++r]=0,Qy[r]=0; add(0,0); int x,y,sx,sy; while (l<r && cnt<LIM){ x=Qx[++l],y=Qy[l],sx,sy; for (int k=0;k<4;k++){ sx=x+_dx[k],sy=y+_dy[k]; if (!ask(sx,sy) && Map[(sx%n+n)%n][(sy%m+m)%m]=='.'){ Qx[++r]=sx,Qy[r]=sy; add(sx,sy); if (sx%n==0 && sy%m==0) cnt++; if (r==M-1) return; } } } } inline ll Abs(ll x) { return x>0?x:-x; } int flag=0; ll dx,dy; inline void Query(int x,int y){ if (cnt<LIM && r<M-1) { printf("%s\n",ask(x,y)?"yes":"no"); return; } if (flag) { printf("%s\n",ask((x%n+n)%n,(y%m+m)%m)?"yes":"no"); return; } int L=-1e9,R=1e9; while (L+5<R){ int m1=(L+L+R)/3,m2=(L+R+R)/3; ll f1=Abs(x+dx*m1)+Abs(y+dy*m1),f2=Abs(x+dx*m2)+Abs(y+dy*m2); if (f1<f2) R=m2; else L=m1; } int k=L; for (int i=L;i<=R;i++) if (Abs(x+dx*k)+Abs(y+dy*k)>=Abs(x+dx*i)+Abs(y+dy*i)){ if (ask(x+dx*i,y+dy*i)) return void(printf("yes\n")); k=i; } printf("no\n"); } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(m); for (int i=0;i<n;i++) read(Map[i]); bfs(); if (cnt>=LIM || r==M-1){ if (ask(n,0) && ask(0,m)) flag=1; else{ dx=1LL<<40,dy=1LL<<40; for (int i=1;i<=r;i++) if (Qx[i]%n==0 && Qy[i]%m==0) if (Qx[i]+Qy[i]<dx+dy) dx=Qx[i],dy=Qy[i]; } } int Q,x,y; read(Q); while (Q--){ read(x); read(y); Query(x,y); } return 0; }