没想到二分图博弈这么早就考了？
首先我们发现，如果将和起点行列之和奇偶性一样的点设为黑色，其余设为白色，那么每次空格只会在异色边之间走，而不会在同色边之间走。
这就类似于一个二分图，更具体的，如果一个黑色方格上面的棋子是X（认为起点也是X），一个白色放个上面的棋子是O，且两者相邻，则两者之间有一条边。双方只能每次走一条边，且走过的点不能再走。二分图博弈的结论是：对于某个点，删掉这个点以后如果和没删掉之前最大匹配数不一样，则先手必胜，否则后手必胜。
考虑如何证明。首先，这个条件相当于如果起点一定在最大匹配中，那么必胜。考虑一个一定在最大匹配中的点，这表明这个点所延伸出的交错路中，至少有一条长度为奇数。则先手可以向这条路走，则先手可必胜。
对于这道题来说只需倒着加点，每次在残量网络上增广即可。时间复杂度\(O(knm)\)
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=2e3+5,M=N*N*2+5,K=1e5+5,mod=998244353,Mod=mod-1;const ll INF=2e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,x,y,X[N],Y[N],A[N][N],Fl[N][N],W[N],Ans[N],Ah,S,T;char c[N];
int xp[4]={1,0,-1,0},yp[4]={0,1,0,-1};
struct yyy{int to,w,z;};struct ljb{int head=1,h[N];yyy f[M];void add(int x,int y,int z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}}s;
void con(int x,int y,int z){/*cerr<<x<<' '<<y<<'\n';*/s.add(x,y,z);s.add(y,x,0);}
namespace Dicnic{
int d[N],Ns[N];queue<int> Q;
int BFS(){
while(!Q.empty()) Q.pop();Me(d,0x3f);d[S]=0;Q.push(S);Ns[S]=s.h[S];while(!Q.empty()){
int x=Q.front();/*cerr<<x<<'\n';*/Q.pop();yyy tmp;for(int i=s.h[x];i;i=tmp.z){
tmp=s.f[i];if(!tmp.w||d[tmp.to]<=d[x]+1) continue;d[tmp.to]=d[x]+1;Q.push(tmp.to);Ns[tmp.to]=s.h[tmp.to];
if(tmp.to==T) return 1;
}
}return 0;
}
int DFS(int x,int Sum){
if(x==T) return Sum;int i,k,pus=0;yyy tmp;for(int i=Ns[x];i;i=tmp.z){
tmp=s.f[i];Ns[x]=i;if(!tmp.w||d[tmp.to]!=d[x]+1) continue;k=DFS(tmp.to,min(tmp.w,Sum));if(!k) d[tmp.to]=1e9;
s.f[i].w-=k;s.f[i^1].w+=k;pus+=k;Sum-=k;if(!Sum) break;
}return pus;
}
int calc(){int Ans=0;while(BFS()) Ans+=DFS(S,1e9);/*cerr<<'\n';*/return Ans;}
}
int main(){
freopen("1.in","r",stdin);
int i,j,h;scanf("%d%d",&n,&m);T=n*m+1;for(i=1;i<=n;i++) for(scanf("%s",c+1),j=1;j<=m;j++) c[j]^'.'?(A[i][j]=(c[j]=='O')):(X[0]=i,Y[0]=j);
scanf("%d",&k);for(i=1;i<=2*k;i++) scanf("%d%d",&X[i],&Y[i]),Fl[X[i]][Y[i]]=1;Fl[X[0]][Y[0]]=1;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) if(!Fl[i][j]){
if((i+j-X[0]-Y[0])&1)con(d(i,j),T,1);else {
con(S,d(i,j),1);if(!A[i][j])for(h=0;h<4;h++) {
int x=i+xp[h],y=j+yp[h];if(x<1||y<1||x>n||y>m||Fl[x][y]||!A[x][y]) continue;
con(d(i,j),d(x,y),1);
}
}
}
}
for(i=2*k;~i;i--){
if(i&1) {
con(d(X[i],Y[i]),T,1);if(A[X[i]][Y[i]])for(h=0;h<4;h++){
x=X[i]+xp[h],y=Y[i]+yp[h];if(x<1||y<1||x>n||y>m||Fl[x][y]||A[x][y]) continue;
con(d(x,y),d(X[i],Y[i]),1);
}
}else{
con(S,d(X[i],Y[i]),1);if(!A[X[i]][Y[i]])for(h=0;h<4;h++) {
int x=X[i]+xp[h],y=Y[i]+yp[h];if(x<1||y<1||x>n||y>m||Fl[x][y]||!A[x][y]) continue;
con(d(X[i],Y[i]),d(x,y),1);
}
}Fl[X[i]][Y[i]]=0;
Ans[i]=Ans[i+1]+Dicnic::calc();
}
for(i=1;i<=k;i++) Ans[2*i-2]^Ans[2*i-1]&&Ans[2*i-1]^Ans[2*i]&&(Ans[++Ah]=i);printf("%d\n",Ah);for(i=1;i<=Ah;i++) printf("%d\n",Ans[i]);
}