うーん、典型っぽい問題。
https://community.topcoder.com/stat?c=problem_statement&pm=17603&rd=19234
問題
H*Wのグリッドが与えられる。
一部のマスは障害物がある。
障害物のないマスをN個選び、芋を植えたい。
ただし、隣接するマス同士で芋を植えてはならない。
条件を満たす植え方の1例を示せ。
解法
グリッドを二部グラフとみなし、最大独立集合がN点以上ならば良い。
求め方はけんちょん氏のQiita記事が参考になる。
qiita.com
ちなみに、最大独立集合の頂点数だけを求める問題はAtCoderで過去に出ている。
https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c
template<class V> class MaxFlow_dinic { public: struct edge { int to,reve;V cap;}; static const int MV = 3000; vector<edge> E[MV]; int itr[MV],lev[MV]; void add_edge(int x,int y,V cap,bool undir=false) { E[x].push_back((edge){y,(int)E[y].size(),cap}); E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0}); } void bfs(int cur) { MINUS(lev); queue<int> q; lev[cur]=0; q.push(cur); while(q.size()) { int v=q.front(); q.pop(); FORR(e,E[v]) if(e.cap>0 && lev[e.to]<0) lev[e.to]=lev[v]+1, q.push(e.to); } } V dfs(int from,int to,V cf) { if(from==to) return cf; for(;itr[from]<E[from].size();itr[from]++) { edge* e=&E[from][itr[from]]; if(e->cap>0 && lev[from]<lev[e->to]) { V f=dfs(e->to,to,min(cf,e->cap)); if(f>0) { e->cap-=f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(int from, int to) { V fl=0,tf; while(1) { bfs(from); if(lev[to]<0) return fl; ZERO(itr); while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf; } } }; int vis[2500]; class Potatoes { public: vector <string> plant(vector <string> F, int N) { MaxFlow_dinic<int> mf; int H=F.size(); int W=F[0].size(); int y,x; FOR(y,H) FOR(x,W) if(F[y][x]=='.') { if((y+x)%2==0) { mf.add_edge(2500,y*50+x,1); int i; int d[4]={0,1,0,-1}; FOR(i,4) { int ty=y+d[i]; int tx=x+d[i^1]; if(ty>=0&&ty<H&&tx>=0&&tx<W) mf.add_edge(y*50+x,ty*50+tx,1); } } else { mf.add_edge(y*50+x,2501,1); } } int tar=mf.maxflow(2500,2501); ZERO(vis); queue<int> Q; FOR(y,H) FOR(x,W) if(F[y][x]=='.') { if((y+x)%2==0) { FORR(e,mf.E[y*50+x]) if(e.to==2500&&e.cap==0) { vis[y*50+x]=1; Q.push(y*50+x); } } } while(Q.size()) { int cur=Q.front(); Q.pop(); FORR(e,mf.E[cur]) if(e.to<2500&&e.cap==1&&vis[e.to]==0&&F[e.to/50][e.to%50]=='.') { vis[e.to]=1; Q.push(e.to); } } cout<<N<<" "<<tar<<endl; FOR(y,H) FOR(x,W) if(N&&F[y][x]=='.') { if((y+x)%2==0) { if(vis[y*50+x]==1) F[y][x]='P', N--; } else { if(vis[y*50+x]==0) F[y][x]='P', N--; } } cout<<N<<endl; if(N) return {}; return F; } }
まとめ
解法はすぐ思いついたけど、実装が手間だった。
最大独立集合を求めるコード、過去に書いたことなかったかな…。