SoundHound Inc. Programming Contest 2018 (春) C - 広告 (400)

C - 広告

概要

R × Cマスのグリッドが与えられる。グリッドは . か * で構成される。
. のマスに広告を配置させることを考える。ただし、広告は他の広告と上下左右で隣接しないように配置したい。
配置できる広告の最大値を求めよ。

制約

1 ≦ R, C ≦ 40

方針

グリッドは . のマスを頂点とし、上下左右に隣接した頂点同士を辺で結ぶことにより、グラフを構成する。（グリッドグラフ）
グリッドグラフは二部グラフである。なぜならグリッドを市松模様で塗ると同じ色のグリッドの間に辺が存在しないため、この塗分けにより頂点を2つのグループに分けることが出来るためである。

広告を他の広告と上下左右で隣接しないように配置するということは、辺で結ばれていない頂点を選んでいくことであり、これは二部グラフの最大安定集合を求めることである。最大安定集合のサイズは「頂点数 - 最大マッチング数」で求めることができる。

感想

方針は下記を参考にしました。
drken1215.hatenablog.com

二部グラフの最大マッチングのライブラリは下記を参考にしました。
ei1333.github.io

解答

Submission #8318252 - SoundHound Inc. Programming Contest 2018 (春)

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
// 2部グラフの最大マッチングを求める
// 片方の頂点サイズをn, もう片方の頂点サイズをmで入力する
struct HopcroftKarp {
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;
 
  HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}
 
  void add_edge(int u, int v) {
    graph[u].push_back(v);
  }
 
  void bfs() {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }
 
    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }
 
  bool dfs(int a) {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }
 
  int bipartite_matching() {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }
 
  void output() {
    for(int i = 0; i < match.size(); i++) {
      if(~match[i]) {
        cout << match[i] << "-" << i << endl;
      }
    }
  }
};
 
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int r, c;
	cin >> r >> c;
 
	string grid[r];
	rep(i, r) cin >> grid[i];
 
	int V = r * c;
	HopcroftKarp hk(V, V);
 
	rep(i, r) rep(j, c){
		int left = i * c + j;
		if(grid[i][j] == '*'){
			V--;
			continue;
		}
 
		if((i + j) % 2 == 1) continue;
		rep(d, 4){
			int ni = i + dx[d], nj = j + dy[d];
			if(ni < 0 || ni >= r || nj < 0 || nj >= c) continue;
			if(grid[ni][nj] == '*') continue;
 
			int right = ni * c + nj;
			hk.add_edge(left, right);
		}
	}
 
	int mat = hk.bipartite_matching();
	cout << V - mat << endl;
}

ちなみにこちらは、最初に考えたうまくいかない貪欲法です。（WA）
Submission #8306186 - SoundHound Inc. Programming Contest 2018 (春)

どうしてダメなのか要確認です。