萌新求助 abc g

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 305;
vector<int> g2[N * N],g3[N * N];
bool vis[N * N],vis2[N * N],vis3[N * N],vis4[N * N];
map<pair<int,int>,int> mp;
int n,a,b,xx[4] = {1,-1,1,-1},yy[4] = {1,1,-1,-1},num[N * N],s,t;
char s2[N][N];
template<int N,int M>
struct MaxFlow{
	int head[N],thead[N],cnt = 1,n,dis[N];
	struct node{int u,v,w,nxt;}e[M << 1];
	queue<int> q;
	void clear(){cnt = 1;while(n)head[n--] = 0;}
	void save(int u,int v,int w){n = max({n,u,v});e[++cnt] = {u,v,w,head[u]},head[u] = cnt;if(u != s && u != t && v != s && v != t)g2[u].push_back(v);}
	void add(int u,int v,int w){save(u,v,w),save(v,u,0);}
	bool test(int x){return !e[x * 2].w;} 
	bool bfs(int s,int t){
		memset(dis,-1,sizeof(int) * (n + 1));
		dis[s] = 0;while(!q.empty())q.pop();q.push(s);
		while(!q.empty()){
			int u = q.front();q.pop();
            if(u == t)break;
			for(int i = head[u];i;i = e[i].nxt){
				int v = e[i].v,w = e[i].w;
				if(w && dis[v] == -1)dis[v] = dis[u] + 1,q.push(v);
			}
		}
		for(int i = 1;i <= n;i++)thead[i] = head[i];
		return ~dis[t];
	}
	int dfs(int u,int flow,int t){
		if(u == t)return flow;
		int lst = flow;
		for(int &i = thead[u];i;i = e[i].nxt){
            if(!lst)continue;
			int v = e[i].v,w = e[i].w;
			if(dis[u] + 1 == dis[v] && w){
				int tmp = dfs(v,min(lst,w),t);
				e[i].w -= tmp,e[i ^ 1].w += tmp,lst -= tmp;
			}
		}
		return flow - lst;
	}
	int flow(int s,int t){
		int ans = 0;
		while(bfs(s,t))ans += dfs(s,(int)(1e15),t);
		return ans;
	}
};
MaxFlow<N * N,N * N * 11> g;
void dfs(int u,int now = 0){
	if(vis[u])return;
	vis[u] = true;
	//cout << u << endl;
	for(auto v : g2[u]){
		if(mp.count(make_pair(u,v)) == now)dfs(v,now ^ 1);//,cout << u << "->" << v << endl;
	}
}
void dfs2(int u){
	if(vis4[u])return;
	vis4[u] = true;
	for(auto v : g3[u]){
		num[v] = num[u] ^ 1;
		dfs2(v);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> a >> b;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			for(int k = 0;k < 4;k++){
				int tx = i + xx[k] * a,ty = j + yy[k] * b;
				if(tx < 1 || tx > n || ty < 1 || ty > n)continue;
				g3[(i - 1) * n + j].push_back((tx - 1) * n + ty);
			}
			for(int k = 0;k < 4;k++){
				int tx = i + xx[k] * b,ty = j + yy[k] * a;
				if(tx < 1 || tx > n || ty < 1 || ty > n)continue;
				g3[(i - 1) * n + j].push_back((tx - 1) * n + ty);
			}
		}
	} 
	for(int i = 1;i <= n * n;i++){
		if(!vis4[i])dfs2(i);
	}
	s = n * n + 1,t = n * n + 2;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			cin >> s2[i][j];
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			int p = (i - 1) * n + j;
//			cout << p << " " << num[p] << endl;
			if(s2[i][j] == '.'){
				if(!num[p])g.add(s,p,1);
				else g.add(p,t,1);
				for(int k = 0;k < 4;k++){
					int tx = i + xx[k] * a,ty = j + yy[k] * b;
					if(tx < 1 || tx > n || ty < 1 || ty > n)continue;
					if(!(i < tx || (i == tx && j < ty)))continue;
					if(s2[tx][ty] == '#')continue;
					assert(num[p] != num[(tx - 1) * n + ty]);
					if(num[p])g.add((tx - 1) * n + ty,p,1);
					else g.add(p,(tx - 1) * n + ty,1);
				}
				for(int k = 0;k < 4;k++){
					int tx = i + xx[k] * b,ty = j + yy[k] * a;
					if(tx < 1 || tx > n || ty < 1 || ty > n)continue;
					if(!(i < tx || (i == tx && j < ty)))continue;
					if(s2[tx][ty] == '#')continue;
					assert(num[p] != num[(tx - 1) * n + ty]);
					if(num[p])g.add((tx - 1) * n + ty,p,1);
					else g.add(p,(tx - 1) * n + ty,1);
				}
			}
		}
	}
//	cout << g.flow(s,t) << endl;
	g.flow(s,t);
	for(int i = 1;i <= n * n;i++){
		if(!num[i])vis3[i] = true;
	}
	for(int i = 2;i <= g.cnt;i++){
		if(i % 2 == 0 && !g.e[i].w){
			if(g.e[i].u == s)vis3[g.e[i].v] = false;
			else if(g.e[i].v != t)mp[{g.e[i].u,g.e[i].v}] = mp[{g.e[i].v,g.e[i].u}] = true;//,cout << g.e[i].u << " " << g.e[i].v << endl;
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if(vis3[(i - 1) * n + j] && !vis[(i - 1) * n + j])dfs((i - 1) * n + j);
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if(s2[i][j] == '.'){
				//cout << i << " " << j << " " << num[(i - 1) * n + j] << " " << vis[(i - 1) * n + j] << endl;
			}
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if(s2[i][j] == '#')cout << "#";
			else if(s2[i][j] == '.'){
				cout << ((num[(i - 1) * n + j] && vis[(i - 1) * n + j]) || (!num[(i - 1) * n + j] && !vis[(i - 1) * n + j]) ? '.' : 'o');
			}
		}
		cout << endl;
	}
}