看到数据范围被吓傻了。
根据题解可得。。我们把原来的网格图转成它的对偶图。。。删边就变成了连边，判联通就变成判不联通了。。
联通什么的自然就用并查集了。。。
具体细节的话还是自己画图靠谱多了
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=1504; 6 int fa[maxn*maxn]; 7 int i,j,k,n,m,last,n1,sm,q,x,y,x1,y1; 8 char s1[3],s[3]; 9 10 int ra;char rx; 11 inline int read(){ 12 rx=getchar(),ra=0; 13 while(rx<'0'||rx>'9')rx=getchar(); 14 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 15 } 16 17 inline int getfa(int x){ 18 return fa[x]!=x?fa[x]=getfa(fa[x]):x; 19 } 20 inline void run(int x,int y,char id){ 21 int a=x*n1+y+1,b=a-(id=='N'?n1:1); 22 x=getfa(a),y=getfa(b); 23 if(x==y)puts("NIE"),last=0;else fa[x]=y,puts("TAK"),last=1; 24 } 25 int main(){ 26 n=read(),q=read(); 27 n1=n+1,sm=n1*n1; 28 for(i=1;i<=sm;i++)fa[i]=i; 29 for(i=1;i<=n1;i++)fa[i]=fa[i*n1]=fa[i*n1+1]=fa[sm-i]=1; 30 last=1; 31 while(q--){ 32 x=read(),y=read(),scanf("%s",s),x1=read(),y1=read(),scanf("%s",s1); 33 if(last==1)run(x,y,s[0]);else run(x1,y1,s1[0]); 34 } 35 return 0; 36 }