题目
分析：
把移动的过程看做是中间空格在走，则空格一定是在黑格子与白格子间交替移动，这就变成了一个二分图的模型。
通过题目可以得出两个性质：
1.棋盘上的每一点最多只被走一次
2.如果兔兔将要移动的空格对应的点一定在二分图的最大匹配上，兔兔必胜。
性质2的原因口胡：空格在最大匹配中，那么沿着匹配边走一个点，一定能走到下一个黑点，而黑点不一定能找到下一条边走到白点，兔兔必胜。
如何判断那个点是否一定在最大匹配上呢？
如果强制把那个点去掉，看是否能找到增广路，如果不能，就说明那个点一定在最大匹配上。
但是题中要求的是错误步骤，应该怎么转换呢？
把走的每一步转换成一个新的局面，然后通过上述性质去check此局面是先手必胜还是必败。
#include<bits/stdc++.h> using namespace std; #define ri register int #define N 2500 #define nn 50 int id[nn][nn],a[nn][nn],fl[N],to[N<<1],nex[N<<1],head[N],mat[N],vis[N],ans[N],win[N]; int dx[5]={0,0,1,-1},dy[5]={1,-1,0,0},tot=0,T=0; char s[nn]; int read() { int x=0,fl=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') fl=-1; ch=getchar(); } while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar(); return x; } void add(int a,int b) { to[++tot]=b; nex[tot]=head[a]; head[a]=tot; } bool dfs(int x) { if(fl[x]) return false;//被删除的点不会再被遍历到 for(ri i=head[x];i;i=nex[i]){ int v=to[i]; if(fl[v] || vis[v]==T) continue; vis[v]=T; if(!mat[v] || dfs(mat[v])){ mat[x]=v; mat[v]=x;//最好记录两边 保证不重不漏 return true; } } return false; } int main() { //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); int n,m,x,y,cnt=0; n=read(); m=read(); for(ri i=1;i<=n;++i) for(ri j=1;j<=m;++j) id[i][j]=++cnt; for(ri i=1;i<=n;++i){ scanf("%s",s); for(ri j=1;j<=m;++j){ a[i][j]=(s[j-1]=='O')?0:1; if(s[j-1]=='.') x=i,y=j; } } for(ri i=1;i<=n;++i) for(ri j=1;j<=m;++j) for(ri k=0;k<=3;++k){ if(a[i][j]==0) continue;//保证是黑点向白点连边 int xx=i+dx[k],yy=j+dy[k]; if(xx<1 || xx>n || yy<1 || yy>m || a[xx][yy]==1) continue; add(id[i][j],id[xx][yy]),add(id[xx][yy],id[i][j]); } for(ri i=1;i<=n;++i) for(ri j=1;j<=m;++j) if(a[i][j]==0){ ++T; dfs(id[i][j]); } //题目中给了每一次的移动方式 其实可以转变成：每一次在走完之前步后的剩余棋盘下 判断是否可以先手必胜 int op=read(); cnt=0; for(ri i=1;i<=op*2;++i){ int now=id[x][y]; fl[now]=1;//打标记说明这个点已经被去掉 if(mat[now]){ int v=mat[now]; mat[now]=mat[v]=0; ++T;//++T是为了判断有没有绕环 所以每dfs一次都要++T win[i]= !dfs(v);//如果dfs成功了 说明可以找到一条不包含now的增广路 now是必败点 标记成 0 } //如果这个点直接没有在最大匹配中 就应该为必败点 x=read(),y=read(); } //如果兔兔本来这步可以赢 就说明这一步它走错了 因为最后一定是兔兔必输状态 //根据题意判断两次 for(ri i=1;i<=op;++i) if( win[i<<1] && win[(i<<1)-1] ) ans[++cnt]=i; printf("%d ",cnt); for(ri i=1;i<=cnt;++i) printf("%d ",ans[i]); return 0; } /* 4 OOXX OXXO OO.O XXXO 2 2 2 3 */