注意到每个位置只能右转一次，首先考虑如果图没有障碍那么显然要走螺旋形的
然后现在有障碍，容易发现对于某个位置如果既可以直走又可以右转，那么一定会选择直走
因为如果转了以后就一定没法走到原本直走可以走到的位置，所以必须直走
那么思路就很明确了，按这种走法然后看看走到底以后经过的总的格子数是不是等于没有障碍的格子数
但是暴力显然会 $T$ 飞
所以对每一行每一列维护一个 $vector$ ，每次走直接在 $vector$ 上二分出第一个走到的障碍，然后就可以了
实现的时候会注意到走过的位置会因为没有障碍重复走
但是因为我们在绕圈的时候走的矩形是越来越小的，所以维护一下外层的矩形就行了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int n,m,K; ll ans; vector <int> X[N],Y[N]; int main() { n=read(),m=read(),K=read(); for(int i=1;i<=K;i++) { int a=read(),b=read(); X[a].push_back(b); Y[b].push_back(a); } for(int i=1;i<=n;i++) sort(X[i].begin(),X[i].end()); for(int i=1;i<=m;i++) sort(Y[i].begin(),Y[i].end()); int x=1,y=1,k=1,flag=0; ans++; int xL=0,xR=n+1,yL=0,yR=m+1; while(233) { int tx=0,ty=0; if(k==1) { tx=x,ty=lower_bound(X[x].begin(),X[x].end(),y)-X[x].begin(); if(ty==X[x].size()) ty=yR-1; else ty=min(yR-1,X[x][ty]-1); k=2; xL=x; } else if(k==2) { tx=lower_bound(Y[y].begin(),Y[y].end(),x)-Y[y].begin(),ty=y; if(tx==Y[y].size()) tx=xR-1; else tx=min(xR-1,Y[y][tx]-1); k=3; yR=y; } else if(k==3) { tx=x,ty=lower_bound(X[x].begin(),X[x].end(),y)-X[x].begin()-1; if(ty<0) ty=yL+1; else ty=max(yL+1,X[x][ty]+1); k=4; xR=x; } else if(k==4) { tx=lower_bound(Y[y].begin(),Y[y].end(),x)-Y[y].begin()-1,ty=y; if(tx<0) tx=xL+1; else tx=max(xL+1,Y[y][tx]+1); k=1; yL=y; } if(x==tx&&y==ty&&flag) break; ans+=abs(x-tx)+abs(y-ty); x=tx,y=ty; flag=1; } if(ans>1ll*n*m-K) cout<<"GG"; if(ans==1ll*n*m-K) printf("Yes\n"); else printf("No\n"); return 0; }
Codeforces 1236D. Alice and the Doll
原文：https://www.cnblogs.com/LLTYYC/p/11706073.html