题解

图论建模

把棋盘上的格子看成图的顶点，相邻格子连边。棋子只分黑白两色，移动规则要求：

• 轮到兔兔（白子）时，只能把与空格相邻的白子推向空格；
• 轮到蛋蛋（黑子）时，只能推黑子。

这等价于在二部图 $G=(X,O)$ 上移动一个“空位”：空位位于 $X$ 部分时，白方只能沿一条 $X\to O$ 的边走到某个白子所在的位置，下一步空位就落入 $O$，只能由黑方沿 $O\to X$ 的边行动。该博弈是“交替沿边移动空位”的正常型博弈，其胜负关系仅由当前空位在最大匹配中的地位决定：

• 若在 $X\cup\{\text{空位}\}$ 与 $O$ 构成的二部图上，把空位纳入可配对集合后最大匹配数增加了，则存在一条以空位为起点的增广路，当前行动方有必胜策略；
• 否则，空位所有走法都会被对手以对称方式追平，当前行动方必败。

这个结论可由 König 定理与“博弈图 = 交替路径树”推出。

动态维护匹配

棋盘规模只有 $40\times40$，但要判断 $k\le 1000$ 次操作。直接重建整个匹配较慢，因此程序中维护一份全局的最大匹配：

1. 在当前局面下构造“左侧 = 当前行动方的棋子及空位，右侧 = 对方棋子”的图，并调用 BFS 版匈牙利算法增广到极大；
2. 再把空位从左侧移除、重新增广一次；若两次的匹配大小不同，则当前玩家有必胜策略；
3. 交换玩家颜色重复上述步骤，就能判断下一手是否必胜；
4. 每次交换空位与棋子时，只需把它们涉及的匹配边删除即可，避免了完全重建。

若在兔兔行动前 res1 != res2 而在她落子后（轮到蛋蛋时）res3 == res4，说明她把必胜局面变成了必败局面，此次操作就是“失误”。按题意输出所有此类编号即可。

复杂度

棋盘节点数最多 $1600$，匈牙利算法单次增广 $O(E\sqrt{V})$，实际常数较小。我们在每个回合只对变化位置邻域重建边集，因此 $k \le 1000$ 仍能很快跑完。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 41;
const int MXV = 1601;
const int ways[][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int n, m, k;
char s[MXN][MXN];
vector< int > ns;
vector< int > g[MXV];
int px, py, res, match[MXV], pre[MXV];
bool lft[MXV];
queue< int > q;

int read(){
	int x = 0;
	char c = getchar();
	for(;c < '0' || c > '9';) c = getchar();
	for(;c >= '0' && c <= '9';c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x;
}

int trn(int x, int y){
	return (x - 1) * m + y;
}

bool chck(int x, int y){
	return x && x <= n && y && y <= m;
}

void clear(){
	int i, j;
	for(i = 1;i <= n * m;++i) g[i].clear();
}

void erase(int x, int y){
	if(match[trn(x, y)]){
		--res;
		match[match[trn(x, y)]] = 0;
		match[trn(x, y)] = 0;
	}
}

bool bfs(){
	int i;
	for(i = 1;i <= n * m;++i) pre[i] = 0;
	for(i = 1;i <= n * m;++i)
		if(lft[i] && match[i] == 0) q.push(i);
	for(;q.size();){
		int x = q.front();
		q.pop();
		for(auto y : g[x])
			if(match[y] == 0){
				pre[y] = x;
				for(;y;){
					int nxt = match[pre[y]];
					match[y] = pre[y];
					match[pre[y]] = y;
					y = nxt;
				}
				for(;q.size();) q.pop();
				return 1;
			}
			else if(pre[y] == 0){
				pre[y] = x;
				q.push(match[y]);
			}
	}
	return 0;
}

int work(){
	for(;bfs();) ++res;
	return res;
}

int main(){
	int i, j, l, t;
	n = read();
	m = read();
	for(i = 1;i <= n;++i){
		scanf("%s", s[i] + 1);
		for(j = 1;j <= m;++j)
			if(s[i][j] == '.'){
				px = i;
				py = j;
			}
	}
	k = read();
	for(t = 1;t <= k;++t){
		clear();
		for(i = 1;i <= n;++i)
			for(j = 1;j <= m;++j)
				if(s[i][j] != 'O'){
					lft[trn(i, j)] = 1;
					for(l = 0;l < 4;++l){
						int nx = i + ways[l][0], ny = j + ways[l][1];
						if(chck(nx, ny) && s[nx][ny] == 'O') g[trn(i, j)].push_back(trn(nx, ny));
					}
				}
				else lft[trn(i, j)] = 0;
		int res1 = work();
		erase(px, py);
		clear();
		for(i = 1;i <= n;++i)
			for(j = 1;j <= m;++j)
				if(s[i][j] == 'X'){
					lft[trn(i, j)] = 1;
					for(l = 0;l < 4;++l){
						int nx = i + ways[l][0], ny = j + ways[l][1];
						if(chck(nx, ny) && s[nx][ny] == 'O') g[trn(i, j)].push_back(trn(nx, ny));
					}
				}
				else lft[trn(i, j)] = 0;
		int res2 = work();
		int tx = px, ty = py;
		px = read();
		py = read();
		swap(s[tx][ty], s[px][py]);
		erase(tx, ty);
		erase(px, py);
		clear();
		for(i = 1;i <= n;++i)
			for(j = 1;j <= m;++j)
				if(s[i][j] != 'X'){
					lft[trn(i, j)] = 1;
					for(l = 0;l < 4;++l){
						int nx = i + ways[l][0], ny = j + ways[l][1];
						if(chck(nx, ny) && s[nx][ny] == 'X') g[trn(i, j)].push_back(trn(nx, ny));
					}
				}
				else lft[trn(i, j)] = 0;
		int res3 = work();
		erase(px, py);
		clear();
		for(i = 1;i <= n;++i)
			for(j = 1;j <= m;++j)
				if(s[i][j] == 'O'){
					lft[trn(i, j)] = 1;
					for(l = 0;l < 4;++l){
						int nx = i + ways[l][0], ny = j + ways[l][1];
						if(chck(nx, ny) && s[nx][ny] == 'X') g[trn(i, j)].push_back(trn(nx, ny));
					}
				}
				else lft[trn(i, j)] = 0;
		int res4 = work();
		if(res1 != res2 && res3 != res4) ns.push_back(t);
		tx = px;
		ty = py;
		px = read();
		py = read();
		swap(s[tx][ty], s[px][py]);
		erase(tx, ty);
		erase(px, py);
	}
	printf("%d\n", (int)ns.size());
	for(auto x : ns) printf("%d\n", x);
	return 0;
}