本文共 1161 字，大约阅读时间需要 3 分钟。

题解

今天来学了一波平面图转对偶图。。

#include
   
    #include
    
     #include
     
      using namespace std;const int N=1505;int M;int f[N*N];int n,k;int m;int last=1;int find (int x){
  return f[x]==x?f[x]:f[x]=find(f[x]);}int P (int x,int y){
  return (x-1)*m+y;}void Ins (int x,int y)//这两个点连通 {    int fx=find(x),fy=find(y);    f[fx]=fy;}void solve (int x,int y,char ch){    int a,b;    if (ch=='E') a=P(x+1,y),b=P(x+1,y+1);    else a=P(x,y+1),b=P(x+1,y+1);    int fx=find(a),fy=find(b);    if (fx==fy)    {        last=0;        printf("NIE\n");    }    else    {        last=1;        f[fx]=fy;        printf("TAK\n");    }}int main(){    scanf("%d%d",&n,&k);    m=n+1;M=m*m;    for (int u=1;u<=M;u++) f[u]=u;    for (int u=2;u<=m;u++) Ins(P(1,u),P(1,u-1));    for (int u=2;u<=m;u++) Ins(P(m,u),P(m,u-1));    for (int u=2;u<=m;u++) Ins(P(u,1),P(u-1,1));    for (int u=2;u<=m;u++) Ins(P(u,m),P(u-1,m));    while (k--)    {        int a,b,c,d;char ss[5],ss1[5];        scanf("%d%d",&a,&b);scanf("%s",ss);        scanf("%d%d",&c,&d);scanf("%s",ss1);        if (last==1) solve(a,b,ss[0]);        else  solve(c,d,ss1[0]);    }    return 0;}