先把棋盘黑白染色，那么对于O，当且仅当它所处的格子颜色和空格不一样才会移动，X相似，那么对于这些O/X，最多也就是被移动1次而已。同时每次空格每次移动所处颜色都是在改变
那么就是二分图博弈啊。而走一步相当于删除一个点，然后每次就让被删的那个点去找增广路，找到了就必败，反之必胜。
蛋蛋走完必胜，兔兔再走又是必胜就是下错了
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int dx[4]={0,-1,0,1}; const int dy[4]={-1,0,1,0}; struct node { int x,y,next; }a[11000];int len,last[11000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int match[11000]; int ti,v[11000]; bool bo[11000]; bool findmuniu(int x) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]!=ti&&bo[y]==true) { v[y]=ti; if(match[y]==0||findmuniu(match[y])==true) { match[y]=x; match[x]=y; return true; } } } return false; } int n,m,prex,prey,nowx,nowy; char ss[110][110]; int blen,b[11000],aslen,as[11000]; int point(int x,int y){return (x-1)*m+y;} bool win(int x,int y) { int p=point(x,y); bo[p]=false; if(match[p]==0)return false; match[match[p]]=0; ti++; bool bk=(!findmuniu(match[p])); match[p]=0; return bk; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",ss[i]+1); for(int j=1;j<=m;j++) if(ss[i][j]=='.')prex=i,prey=j; } blen=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if((i+j)%2==(prex+prey)%2&&ss[i][j]!='O') { b[++blen]=point(i,j); for(int k=0;k<=3;k++) { int ti=i+dx[k],tj=j+dy[k]; if(ti>0&&ti<=n&&tj>0&&tj<=m&&ss[ti][tj]=='O') ins(point(i,j),point(ti,tj)), ins(point(ti,tj),point(i,j)); } } ti=0;memset(v,0,sizeof(v)); memset(bo,true,sizeof(bo)); for(int i=1;i<=blen;i++) { ti++; findmuniu(b[i]); } int AK; aslen=0; scanf("%d",&AK); for(int i=1;i<=AK;i++) { scanf("%d%d",&nowx,&nowy); int w1=win(prex,prey); int w2=win(nowx,nowy); if(w1&&w2)as[++aslen]=i; scanf("%d%d",&prex,&prey); } printf("%d ",aslen); for(int i=1;i<=aslen;i++) printf("%d ",as[i]); return 0; }