【from new_dtoj 3989: 五子棋（fir）】
题目描述
暂无
题解：
简单模拟
考场明显错误炸了，由于数据水82
具体细节见代码吧
（BC是被吃，C是吃，W是赢，R是删点）
#include <cstdio>
#define N 1005
using namespace std;
int n,k,X[N],Y[N],b[N][N],a[N][N],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vis[N][N];
bool BC(int x,int y,int t){
vis[x][y]=1;
for (int i=0;i<4;i++){
int nx=dx[i]+x,ny=dy[i]+y;
if (vis[nx][ny]) continue;
if (!a[nx][ny]){vis[x][y]=0;return 0;}
if (a[X[t]][Y[t]]==a[nx][ny])
if (!BC(nx,ny,t)){vis[x][y]=0;return 0;}
}
vis[x][y]=0;
return 1;
}
void R(int x,int y,int t){
a[x][y]=0;
for (int i=0;i<4;i++){
int nx=dx[i]+x,ny=dy[i]+y;
if (a[nx][ny]==((t&1)?1:2))
R(nx,ny,t);
}
}
inline void C(int x,int y,int t){
for (int i=0;i<4;i++){
int nx=dx[i]+x,ny=dy[i]+y;
if (a[nx][ny] && a[nx][ny]!=a[x][y] && BC(nx,ny,b[nx][ny]))
R(nx,ny,b[nx][ny]);
}
}
inline bool W(int t){
int c=0,x=X[t],y=Y[t];
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,x--;x=X[t]+1;
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,x++;
if (c>=k) return 1;c=0;x=X[t];y=Y[t];
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,y--;y=Y[t]+1;
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,y++;
if (c>=k) return 1;c=0;x=X[t];y=Y[t];
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,x--,y--;x=X[t]+1;y=Y[t]+1;
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,x++,y++;
if (c>=k) return 1;c=0;x=X[t];y=Y[t];
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,x--,y++;x=X[t]+1;y=Y[t]-1;
while(a[x][y]==a[X[t]][Y[t]] && c<k) c++,x++,y--;
return c>=k;
}
int main(){
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d%d",&X[i],&Y[i]);
for (int i=1;i<=n;i++){
if (a[X[i]][Y[i]]){puts("illegal");return 0;}
if (i&1) a[X[i]][Y[i]]=1;else a[X[i]][Y[i]]=2;
b[X[i]][Y[i]]=i;C(X[i],Y[i],i);
if (BC(X[i],Y[i],i)){puts("illegal");return 0;}
if (W(i)){
if (i&1){printf("ITer %d
",i);return 0;}
else{printf("Kitty %d
",i);return 0;}
}
}
puts("draw");return 0;
}