[Luogu p1971] rabbit and egg game (bipartite game)

Rabbit and egg game

Topic link ：luogu P1971

The main idea of the topic

Give you a two-dimensional grid , There is only one position without chess pieces , There are white or black pieces in other positions .
Then two people take turns , The first hand can move one of the four white chess pieces next to the empty grid , The back hand moves the black chess pieces .
Then those who cannot move lose , Then give you the operation process of two people , Guarantee the backhand to win , Then I ask you what moments have changed from being the first to win to being the first to lose .

Ideas

First of all, if you know the bipartite graph game , You can find that this can be a bipartite graph game model .
（ After all, the grid diagram ）
But there are too many states , Let's consider optimization , Or merge duplicate States , Get rid of useless state .

Then you are watching two people alternate , And everyone applies to different situations , Then you find that this picture is not big .
Can we change the state to the level of graph point size ？ Think about it and you'll find a point. Don't repeat it .
Because you must go out and come back after an even number of times , At this time, another person operates to this point , But you last went out and left your color here , The next person can't get in .

Then with this property , In fact, we don't need to care about the color of other positions , Just set the position of the space directly .
Then the edges are fixed, because the colors around you are actually fixed （ We have to go from a different color to this color , Then the different color is equivalent to being replaced with this color ）
So we can do it .

But this is not an inquiry , But you can understand it as asking whether to win first after each operation （ If the situation before and after the first hand operation is that the first hand will win, the first hand will make a mistake ）.
Then you run so many network flows / Hungary is not very good .
When we think about it once, how did we do it , We deleted some first , Then you can't delete it .

In fact, we can do this in reverse order , First get all deleted , Then add one by one , Get the answers respectively .

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;
}