题目大意

两人博弈，有 n × m ( 1 ≤ n , m ≤ 40 ) n\times m(1\le n,m\le 40)n×m(1≤n,m≤40) 的棋盘，每个格子中可能为空、黑棋或白棋，整个棋盘只有 1 11 个空格。对于兔兔，每次操作将一枚与空格相邻的白色棋子移进空格。对于蛋蛋则相反。给出游戏过程，求出兔兔失误的步骤。

题解

每次操作是棋子与空格交换位置。

研究空格的移动，发现空格移动路径不能自交。当路径自交，代表行动了偶数步。假设空格第一次移动与白子交换，那么第偶数步必须与黑子交换。当空格在第偶数步回到起点，一定是与白子交换，与上句话矛盾，故证明空格路径不能自交。

在上述证明中更进一步，空格在偶数步行动中与黑子交换，在奇数步行动中与白子交换，0 00 也是偶数，那么考虑将空格的初始位置看做黑色（不会随空格移动）。那么这时候你会发现，空格的移动路径就是黑白交替的。

容易想到二分图黑白染色。对矩阵分部，白色一部，黑色（包括空格初始位置）一部，将两部之间能够一步到达的点连边，跑最大匹配。

于是你发现，跟这个题有亿点点像。题解

套用那个题的讨论，得出结论：先手走到非最大匹配必须点上必胜。

如何求这个东西？

首先求出一种匹配方案，当枚举到一个点时，有两种可能：

点 p pp 没有被匹配 点 p pp 被匹配 由于路径不能自交，每次空格走到一个点时，直接删除这个点，以免后面走回这里。

如果点 p pp 没有被匹配，显然是非最大匹配必须点。

如果点 p pp 被匹配，那么就将点 p pp 删去（点 p pp 对应的匹配点失配），然后从点 p pp 的匹配点 q qq 尝试增广，增广成功则 p pp 是非最大匹配必须点。

于是能够轻松求出每个步骤的胜负态（即必胜还是必败）。

回到题目，“兔兔失误的步骤”是什么意思？

其实就是兔兔原本必胜，结果一不小心，操作之后变成蛋蛋必胜了。于是只需要记录每个步骤的胜负态，然后再判断即可。 好了话不多说上coad

#include<bits/stdc++.h>
using namespace std;
const int N = 50, K = 1005;
int n, m, ans, cnt, tot, head[N*N];
char g[N][N];
int match[N*N], res[K*2], win[K*2];
bool vis[N*N], block[N*N], color[N][N];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
struct node {
	int to, nxt;
} edge[N*N*2*4]; 
void addedge(int s, int e) {
	cnt++;
	edge[cnt].to = e;
	edge[cnt].nxt = head[s];
	head[s] = cnt;
	return ;
}

bool dfs(int x) { 
	for(int i = head[x]; i != 0; i = edge[i].nxt) {
		int y = edge[i].to;
		if(block[y] == true){
			continue;}
		if(vis[y] == false) {
			vis[y] = true;
			if(match[y] == 0 || dfs(match[y]) == true) {
				match[y] = x;
				match[x] = y;
				return true;
			}
		}
	}
	return false;
}
int get_id(int x, int y) {
	return (x-1) * m + y;
}
bool check(int x, int y) {
	if(x < 1 || x > n || y < 1 || y > m || color[x][y] == false) {

		return false;
	}
	return true;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> g[i][j];
	int sx, sy;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			if(g[i][j] == 'O') {
				color[i][j] = true;
			} else if(g[i][j] == '.') {
				sx = i;
				sy = j;
			}
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			if(color[i][j] == true)
				continue;
			int cur = get_id(i, j);
			for(int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if(check(nx, ny) == false)
					continue;
				int nxt = get_id(nx, ny);
				addedge(cur, nxt);
				addedge(nxt, cur);
			}
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			if(color[i][j] == false)
				continue;
			memset(vis, 0, sizeof(vis));
			int cur = get_id(i, j);
			if(dfs(cur) == true)
				ans++;
		}
	int k;
	cin >> k;
	for(int i = 1; i <= 2*k; i++) {
		int cur = get_id(sx, sy);
		block[cur] = true;
		if(match[cur] == 0)
			win[i] = false;
		else {
			int nxt =  match[cur];
			match[cur] = match[nxt] = 0;
			memset(vis, 0, sizeof(vis));
			if(dfs(nxt) == true)
				win[i] = false;
			else
				win[i] = true;
		}
		cin >> sx >> sy;
	}
	for(int i = 1; i <= k; i++) {
		if(win[2*i-1] == true && win[2*i] == true) {
			res[++tot] = i;
		}
	}
	cout << tot << endl;
	for(int i = 1; i <= tot; i++) {
		cout << res[i] << endl;
	}
	return 0;
}