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();
}