直接博弈论dfs可以得到75分（然鹅我博弈论学的很pie）
#include<bits/stdc++.h> #define LL long long #define INF 10000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } char s[45]; int lr[]={0,0,1,-1},ud[]={1,-1,0,0},ans[1003],tu[43][43],sg[43]; int X,Y,tot=0,n,m; int dfs(int x,int y,int op) { for(int i=0;i<4;++i) { int xx=x+ud[i],yy=y+lr[i]; if(xx<1||xx>n||yy<1||yy>m||tu[xx][yy]!=op)continue; swap(tu[xx][yy],tu[x][y]); if(!dfs(xx,yy,op^1)){swap(tu[xx][yy],tu[x][y]);return 1;}//往下递归得到每一个局面，判断其为必胜还是必败 swap(tu[xx][yy],tu[x][y]); } return 0; } int main() { // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;++i) { scanf("%s",s+1); for(int j=1;j<=m;++j) { if(s[j]=='X')tu[i][j]=1;//黑棋 else if(s[j]=='.')tu[i][j]=2,X=i,Y=j;//空格 } } int op=read(); for(int i=1;i<=op;++i) { int x=read(),y=read(); sg[i]=dfs(X,Y,0); swap(tu[x][y],tu[X][Y]); X=x;Y=y; if(sg[i]&&dfs(X,Y,1))ans[++tot]=i;//走之前兔兔是必胜态，走之后蛋蛋是必胜态 x=read(),y=read(); swap(tu[x][y],tu[X][Y]); X=x;Y=y; } printf("%d ",tot); for(int i=1;i<=tot;++i) printf("%d ",ans[i]); } /* */
然后正解是二分图。。。哇这谁想得到是二分图
让我们认真分析一下：
每一次顺序移动白格黑格，当最后无法移动停止，且每一个格子只会走过一次（感性感知）相当于是黑白交替格子染色—>想到二分图。
与其说是每次交换空格和其他黑白格，不如说是空格在黑白格上走。（第一步在空格本身上）
我们可以把第一步认为是黑格，然后交替走黑白格，如果最后走到黑格，说明兔兔输了（兔兔移动白格）。
然后二分图匹配保证了最后走到的一定是白格，因为从黑格出发（要求每一条路都是奇数步）
走格子相当于是在增广路上走，如果当前x，y一定在最大匹配上（在增广路上而且没有其他的增广路可以替代它了），说明现在是必胜态。
然后对于每一步进行判断，如果兔兔和蛋蛋的第i步都是必胜态，说明兔兔在走第i步之前是必胜态，走了第i步后蛋蛋就是必胜态了。
满足题目要求，累计答案。
#include<bits/stdc++.h> #define N 43 #define LL long long #define INF 10000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } struct EDGE{ int nextt,to; }w[N*N*4]; char s[N]; int lr[]={0,0,1,-1},ud[]={1,-1,0,0},ans[1003],tu[N][N],head[N*N],ord[N][N],vis[N*N],match[N*N],ban[N*N],win[1003]; int X,Y,tot=0,n,m,ndnum=0,res=0,timer=0; void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } void jian_tu()//建二分图 { for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if(!tu[i][j])continue; for(int k=0;k<4;++k) { int xx=i+ud[k],yy=j+lr[k]; if(xx<1||xx>n||yy<1||yy>m||tu[xx][yy])continue; add(ord[i][j],ord[xx][yy]); add(ord[xx][yy],ord[i][j]); } } } int dfs(int x) { if(vis[x]==timer||ban[x])return 0; vis[x]=timer; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(ban[v])continue; if(!match[v]||dfs(match[v])) { match[v]=x;match[x]=v; return 1; } } return 0; } int main() { // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;++i) { scanf("%s",s+1); for(int j=1;j<=m;++j) { ord[i][j]=++ndnum; if(s[j]=='X')tu[i][j]=1;//黑棋 else if(s[j]=='.')tu[i][j]=2,X=i,Y=j;//空格 } } jian_tu(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(tu[i][j])timer++,dfs(ord[i][j]); int op=read(); for(int i=1;i<=op*2;++i) { int id=ord[X][Y]; ban[id]=1; if(match[id]) { int v=match[id]; match[id]=match[v]=0; ++timer; win[i]=(!dfs(v));//在增广路上且不可代替 } X=read();Y=read(); } for(int i=1;i<=op;++i) if(win[2*i-1]&&win[2*i])ans[++res]=i; printf("%d ",res); for(int i=1;i<=res;++i) printf("%d ",ans[i]); }