Bunny and Eggs Game

Topic link: luogu P1971

Topic

You are given a 2D grid, where only one position has no pawns, and the other positions have either white or black pawns.
Then two people take turns to operate, the first hand can choose one of the four white pieces next to the empty square to move over, and the second hand can move the black piece.
Then the person who can't move loses, and then gives you the operation process of two people to ensure that the second player wins, and then asks you when you have changed from the original first mover to the first mover to lose.

ideas

If you first know the bipartite graph game, you can find that this model can be a bipartite graph game.
(After all, grid map)
But there are too many states, then we consider optimization, or merge duplicate states to remove useless states.

Then you are looking at two people alternating, and each of them applies to different situations, and then you find that the picture is not really big.
Can the state be changed to the level of the size of the map point? Think about it and you will find that a point will not be repeated.
Because you must go out and come back after an even number of times, then at this time, another person has operated to this point, but the last person you went out left his color here, and the next person can't get in.

With this property, we actually don't need to care about the color of other positions, we just need to directly set the state to where the space is.
Then the connection is fixed because the color around you is actually fixed (you have to go from a different color to this color, and then that different color is equivalent to being replaced with this color)
So you can do it.

But you are not asking here once, but you can understand that after each operation, you are asking whether the first move will win (if the situation before the first move and after the operation is both the first move and the first move, it will be a mistake).
Then you run so many network streams / Hungary is not good.
Then when we thought about it once, how did we do it? We first deleted some points, and then we deleted them.

Then we can actually do this in reverse order, delete all of them first, and then add them one by one to get the answers separately.

code

#include<queue>
#include<cstdio>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 45;
char s[N][N];
int n, m, K, tot, S, T;
bool col[N][N], in[N][N], win[2005];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
pair <int, int> del[2005];

int id(int x, int y) {return (x - 1) * m + y;}
bool check(int x, int y) {if (x < 1 || x > n) return 0; if (y < 1 || y > m) return 0; if (col[x][y]) return 0; return 1;}
bool check_(int x, int y) {if (x < 1 || x > n) return 0; if (y < 1 || y > m) return 0; return 1;}

struct Flow {
	struct node {
		int x, to, nxt, op;
	}e[N * N * 500];
	int le[N * N], KK, dis[N * N], lee[N * N];
	queue <int> q;
	
	void add(int x, int y, int z) {
		e[++KK] = (node){z, y, le[x], KK + 1}; le[x] = KK;
		e[++KK] = (node){0, x, le[y], KK - 1}; le[y] = KK;
	}
	
	bool bfs() {
		while (!q.empty()) q.pop();
		for (int i = 1; i <= tot; i++) dis[i] = 0, lee[i] = le[i];
		q.push(S); dis[S] = 1;
		while (!q.empty()) {
			int now = q.front(); q.pop();
			for (int i = le[now]; i; i = e[i].nxt)
				if (!dis[e[i].to] && e[i].x) {
					dis[e[i].to] = dis[now] + 1;
					if (e[i].to == T) return 1;
					q.push(e[i].to);
				}
		}
		return 0;
	}
	
	int dfs(int now, int sum) {
		if (now == T) return sum;
		int go = 0;
		for (int &i = lee[now]; i; i = e[i].nxt)
			if (dis[e[i].to] == dis[now] + 1 && e[i].x) {
				int this_go = dfs(e[i].to, min(sum - go, e[i].x));
				if (this_go) {
					e[i].x -= this_go; e[e[i].op].x += this_go;
					go += this_go; if (go == sum) return go;
				}
			}
		return go;
	}
	
	int dinic() {
		int re = 0;
		while (bfs())
			re += dfs(S, INF);
		return re;
	}
}W;

void Init() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (col[i][j] && !in[i][j]) {
				for (int k = 0; k < 4; k++) {
					int tx = i + dx[k], ty = j + dy[k];
					if (!check(tx, ty) || in[tx][ty]) continue;
					W.add(id(i, j), id(tx, ty), 1);
				}
			}
	W.dinic();
}

int main() {
	scanf("%d %d", &n, &m); tot = id(n, m); S = ++tot; T = ++tot;	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			s[i][j] = getchar(); while (s[i][j] != 'X' && s[i][j] != 'O' && s[i][j] != '.') s[i][j] = getchar();
			if (s[i][j] == '.') del[0] = make_pair(i, j), in[i][j] = 1;
			if (s[i][j] == '.' || s[i][j] == 'X') col[i][j] = 1, W.add(S, id(i, j), 1);
				else W.add(id(i, j), T, 1);
		}
	
	scanf("%d", &K);
	for (int i = 1; i <= K << 1; i++) {
		int x, y; scanf("%d %d", &x, &y); del[i] = make_pair(x, y); in[x][y] = 1;
	}
	
	Init();
	
	for (int i = K << 1; i >= 0; i--) {
		pair <int, int> v = del[i];
		in[v.first][v.second] = 0;
		for (int j = 0; j < 4; j++) {
			int tx = v.first + dx[j], ty = v.second + dy[j];
			if (!check_(tx, ty) || in[tx][ty] || col[v.first][v.second] == col[tx][ty]) continue;
			if (col[v.first][v.second]) W.add(id(v.first, v.second), id(tx, ty), 1);
				else W.add(id(tx, ty), id(v.first, v.second), 1);
		}
		win[i] = W.dinic();
	}
	int ans = 0;
	for (int i = 1; i <= K << 1; i += 2) {
		if (win[i - 1] && win[i]) ans++;
	}
	printf("%d\n", ans);
	for (int i = 1; i <= K << 1; i += 2) {
		if (win[i - 1] && win[i]) {
			printf("%d\n", (i + 1) / 2);
		}
	}
	
	return 0;
}