g 求条

#include<bits/stdc++.h>
#define endl '\n'
#define M 800006
using namespace std;
struct MF_Graph { //by dyc2022
	int head[M],cnt,s,t,now[M],dep[M];
	MF_Graph() {cnt=2;}
	struct Edge {int to,next,w;} E[3000006];
	void addedge(int u,int v,int w) {E[cnt]={v,head[u],w},head[u]=cnt++;}
	void addflow(int u,int v,int w) {addedge(u,v,w),addedge(v,u,0);}
	int bfs()
	{
	    queue<int> q;
	    memset(dep,-1,sizeof(dep));
	    dep[s]=0,now[s]=head[s],q.push(s);
	    while(q.size())
	    {
	        int u=q.front(); q.pop();
	        for(int i=head[u],v,w;i;i=E[i].next)
	        {
	            v=E[i].to,w=E[i].w;
	            if(dep[v]==-1&&w>0)
	            	{dep[v]=dep[u]+1,now[v]=head[v],q.push(v); if(v==t)return 1;}
	        }
	    }
	    return 0;
	}
	int dfs(int u,int fl)
	{
	    if(u==t)return fl;
	    int ret=0;
	    for(int i=now[u],v,w;i&&fl>0;i=E[i].next)
	    {
	        v=E[i].to,w=E[i].w,now[u]=i;
	        if(dep[v]==dep[u]+1&&w>0)
	        {
	            int tmp=dfs(v,min(fl,w));
	            if(!tmp)dep[v]=-1; E[i].w-=tmp,E[i^1].w+=tmp,fl-=tmp,ret+=tmp;
	        }
	    }
	    return ret;
	}
	int getflow() {int ret=0; while(bfs())ret+=dfs(s,1e9); return ret;}
} G;
int n,m,A,B,a[306][306],col[M],eid[M],vis[M],mt[M],ans[M];
struct Edge {int u,v;} E[M];
char ch[M];
inline int id(int x,int y) {return (x-1)*n+y;}
vector<int> yG[M],bG[M];
void color(int u)
{
    for(int v:yG[u])
        if(col[v]==-1)col[v]=col[u]^1,color(v);
        else assert(col[v]^col[u]);
}
void dfs(int u) {vis[u]=1; for(int v:bG[u])if(!vis[v])dfs(v);}
main()
{
    scanf("%d%d%d",&n,&A,&B);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for(int j=1;j<=n;j++)a[i][j]=(ch[j]=='#');
    }
    int dx[]={A,B,B,A};
    int dy[]={B,A,-A,-B};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(!a[i][j])
    {
        for(int k=0;k<4;k++)
        {
            int tx=i+dx[k],ty=j+dy[k];
            if(tx<1||tx>n||ty<1||ty>n||a[tx][ty])continue;
            E[++m]={id(i,j),id(tx,ty)};
            yG[id(i,j)].push_back(id(tx,ty));
            yG[id(tx,ty)].push_back(id(i,j));
        }
    }
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(col[id(i,j)]==-1&&!a[i][j])
            col[id(i,j)]=0,color(id(i,j));
    G.s=n+1,G.t=n+2;
    for(int i=1;i<=n*n;i++)
        if(col[i]==0)G.addflow(G.s,i,1);
        else if(col[i]==1)G.addflow(i,G.t,1);
    for(int i=1;i<=m;i++)
    {
        int u=E[i].u,v=E[i].v;
        if(col[u])swap(u,v);
        assert(col[u]==0&&col[v]==1);
        G.addflow(u,v,1),eid[i]=G.cnt-1;
    }
    int mxfl;
    cerr<<(mxfl=G.getflow())<<endl;
    for(int i=1;i<=m;i++)
    {
        int u=E[i].u,v=E[i].v;
        if(col[u])swap(u,v);
        if(G.E[eid[i]].w)bG[u].push_back(v),mt[v]=1;
        else bG[v].push_back(u);
    }
    for(int i=1;i<=n*n;i++)
        if(col[i]==1&&!mt[i])dfs(i);
    int ccc=0;
    for(int i=1;i<=n*n;i++)
        if((col[i]==0&&!vis[i])||(col[i]==1&&vis[i]))ans[i]=1;
        else if(col[i]==0||col[i]==1)ccc++;
    cerr<<ccc<<endl;
    //assert(ccc==mxfl);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        if(a[i][j])putchar('#');
        else if(ans[id(i,j)])putchar('o');
        else putchar('.');
        if(j==n)putchar(10);
    }
    return 0;
}
//最小点覆盖，就是左边遍历到的结点集合，和右边没遍历到的结点集合的并集。