题目描述：
就像题目名字一样，他们在玩一种类似于五子棋的游戏，只是规则和五子棋有一些不同。 就像五子棋一样，ITer和Kitty依次在棋盘上放置棋子，ITer放置黑子，Kitty放置白子。与五子棋不同的是，当一种颜色的X个棋子组成一行或一列或一个对角线的时候（X不一定等于5），执该颜色的子的玩家胜利。
如图，当X=5时，ITer胜利的三种方法：
下了一会儿后，ITer和Kitty觉得无聊了。于是，他们又加了一个类似围棋的规则：当一个连通分量（四连通）的棋子的四周被另一种棋子围住时，这些棋子就消失了，我们称这些子被“吃掉”了。
如图，三颗白棋的四周都被黑棋围住，所以这三颗棋子就应该消失。成为下图：
现在ITer和Kitty下了N步棋，ITer先手，每次下棋的位置用坐标表示。 现在ITer想知道，下了N步棋后，是否有人赢了，在第几步赢了，是否有不合法的走法。
输入：
输入文件第一行两个正整数N，X，表示下了N步棋，当一种颜色的X个棋子组成一行或一列或一个对角线的时候，执该颜色的子的玩家胜利。 接下来的N行，每行2个正整数Xi，Yi，当i为奇数时，表示ITer在第 i步下在了（Xi，Yi）上，当i为偶数时，表示Kitty在第 i步下在了（Xi，Yi）上。
输出：
如果ITer在前N步赢了，则输出“ITer X”（中间用空格连接），X表示ITer在第几步赢了。 如果Kitty在前N步赢了，则输出“Kitty X”（中间用空格连接），X表示Kitty在第几步赢了。 如果在N步以内有不合法的步，则输出“illegal”。
一步不合法有以下几种情况： 1. 这步下在了已经有棋子的格子上。 2. 在没有吃掉对方棋子的情况下，该步子所在的联通分量的棋子被对方的棋子吃掉。如图1，白子走在了红叉的位置上是不合法的，因为这样会使该联通分量被吃掉。
如图2，如果白子走在红叉的位置上是合法的，因为它吃掉了右边的两个黑子。走完这步后白子不会消失，棋盘上的子变成图3。
请忽视某一个人赢了以后出现的不合法的步。 如果既没有出现不合法的步，又没有决出胜负，则输出“draw”。 假设棋盘是无限的。
数据范围：
Subtask 1 30%：N≤20,X≤5,Xi,Yi≤10。 Subtask 2 70%：N≤1000,X≤10,1≤Xi,Yi≤1000 。
模拟大好题。。。考验细节的码农题。
这里有神犇Jzy(orz)的博客已经讲得很清楚了
#include<bits/stdc++.h> using namespace std; #define in inline #define re register #define rep(i,a,b) for(re int i=a;i<=b;i++) #define repd(i,a,b) for(re int i=a;i>=b;i--) #define For(i,a,b) for(int i=a;i<b;i++) #define _(d) while(d(isdigit(ch=getchar()))) template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;} const int N=1004; const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; int a[N][N],cnt,n,k,C,id[N][N],mx,my; bool vis[N]; bool J(int r,int x,int y,int col,bool is,int fl){ /*if(r==9){ printf("(%d , %d)\n",x,y); }*/ vis[id[x][y]]=1; bool ff=0; For(i,0,4){ int tx=x+dx[i],ty=y+dy[i]; if((!a[tx][ty])||(is&&a[tx][ty]==3-col&&(!vis[id[tx][ty]]) &&(!J(r,tx,ty,3-col,0,0)))) ff=1; } For(i,0,4){ int tx=x+dx[i],ty=y+dy[i]; if(a[tx][ty]==col){ if((!vis[id[tx][ty]])&&J(r,tx,ty,col,is,ff|fl)) ff=1; } } if(ff) return true; if(!is&&!(fl|ff)) a[x][y]=0; return false; } in bool work(int r,int x,int y,int t1,int t2){ int x1=0,x2=0; rep(i,0,k){ if(a[x+i*t1][y+i*t2]==C) x1++; else break; } rep(i,0,k){ if(a[x-i*t1][y-i*t2]==C) x2++; else break; } if(x1+x2-1>=k){ if(C==1) printf("ITer %d\n",r); else printf("Kitty %d\n",r); return 0; } return 1; } int main(){ // freopen("FIR.in","r",stdin); //freopen("FIR.out","w",stdout); g(n),g(k);C=2; rep(i,1,n){ memset(vis,0,sizeof(vis)); C=3-C; int x,y;g(x),g(y);id[x][y]=++cnt; if(a[x][y]){puts("illegal");system;return 0;} a[x][y]=C; memset(vis,0,sizeof(vis)); //dfs(x,y,C,is); if(!J(i,x,y,C,1,0)) {puts("illegal");return 0;} mx=max(mx,x); my=max(my,y); /*rep(i,1,mx){ rep(j,1,my) cout<<a[i][j]<<" "; cout<<endl; } cout<<"---"<<endl;*/ rep(j,-1,1){ rep(l,-1,1){ if(!j&&!l) continue; if(!work(i,x,y,j,l)) return 0; } } } puts("draw"); return 0; }
