首先尝试图论建模，如果两个空格子可以互相攻击就连一条无向边。

此时问题转化成图上最大独立集。

NP-Hard

的，但对于二分图有多项式时间算法。

玩玩样例，大胆猜测图是二分图。

inline">\(\gcd(a,b)\)。

此时如果

然后跑出二分图最大独立集并输出方案即可。

关于二分图最大独立集的求法，需要多步转化：

f[M],hd[M],cur[M],dis[M],gap[M],id[N][N];

pair<int,int>

j){if(i<1||i>n||j<1||j>n||c[i][j]=='#')

inline

w){e[++cnt]={v,w,hd[u]},hd[u]=cnt;e[++cnt]={u,0,hd[v]},hd[v]=cnt;

void

i=hd[u];i;i=e[i].nxt){if(!vis[e[i].v]&&e[i].w)

solve(e[i].v);}

q;q.push(t);dis[t]=1;while(!q.empty()){int

u=q.front();q.pop();++gap[dis[u]];for(int

v=e[i].v;if(e[i^1].w&&!dis[v]){q.push(v),dis[v]=dis[u]+1;}}}

int

&i=cur[u];i;i=e[i].nxt){int

v=e[i].v;if(e[i].w&&dis[v]+1==dis[u]){d=dfs(v,min(flow-used,e[i].w));if(d){e[i].w-=d,e[i^1].w+=d,used+=d;if(used==flow)

return

used;}}}--gap[dis[u]];if(!gap[dis[u]])

dis[s]=m+1;++dis[u],++gap[dis[u]];return

used;

main(){scanf("%d%d%d",&n,&a,&b);rept(i,1,n){scanf("%s",c[i]+1);rept(j,1,n){if(c[i][j]=='.')

id[i][j]=++m,pos[m]={i,j},ans[i][j]='o';else

ans[i][j]='#';}}s=++m,t=++m;rept(i,1,n){rept(j,1,n){if(c[i][j]=='#')

continue;add1(id[i][j],i+a,j+b),add1(id[i][j],i-a,j+b),add1(id[i][j],i+a,j-b),add1(id[i][j],i-a,j-b);add1(id[i][j],i+b,j+a),add1(id[i][j],i-b,j+a),add1(id[i][j],i+b,j-a),add1(id[i][j],i-b,j-a);}}rept(i,1,m-2)

if(!f[i])

f[i]=1,dfs(i);bfs();while(dis[s]<=m){memcpy(cur+1,hd+1,sizeof(int)*m);val+=dfs(s,INF);}solve(s);for(int

ans[pos[v].fi][pos[v].se]='.';}for(int

ans[pos[v].fi][pos[v].se]='.';}rept(i,1,n)