PKU 3020 Antenna Placement
http://poj.org/problem?id=3020
アンテナを*となっているマスを全てカバーするように設置したい。
アンテナは1x2のマスを覆うことができる。最低限必要なアンテナの数を求めろというような問題。
一般グラフマッチング的な問題。
再帰を使ってアンテナの配置を変更しながら置いていく。
string in[40]; int match[400]; bool vis[400]; int h,w; bool augment(int v){ vis[v]=true; rep(i,4){ int nx=v/w+dx[i],ny=v%w+dy[i]; int u=nx*w+ny; if(0>nx || nx>=h || 0>ny || ny>=w || vis[u] || in[nx][ny]=='o')continue; if(match[u]==-1 || !vis[match[u]] &&augment(match[u])){ match[u]=v; match[v]=u; return true; } } return false; } void solve(){ cin>>h>>w; rep(i,h)cin>>in[i]; memset(match,-1,sizeof(match)); int ans=0; rep(i,h)rep(j,w){ memset(vis,0,sizeof(vis)); if(in[i][j]=='o' || match[i*w+j]!=-1)continue; augment(i*w+j); ++ans; } cout<<ans<<endl; } main(){ int t; cin>>t; while(t--)solve(); }