TopCoder Open 2013 Round1A Hard DirectionBoard

問題

hxwマスのグリッドがある。
一番上の列と下の列はループしてつながっていて、
右端と左端もループしてつながっている。

それぞれのマスには上下左右いずれかの向きの矢印が書かれている。
一点からスタートした人は、その矢印に従って移動することを繰り返す。
このとき、どのマスからスタートしても、元のマスに戻ってくるような状態を良い状態と呼ぶ。

このグリッドを良い状態にするために書き換えなければならない矢印の本数の最小値を求めよ。

制約条件

h, w≦15

方針

全てのマスがループの中に入っていることは、
グリッドをグラフにしたとき（マスを頂点に、矢印を有向辺）に、
全ての頂点について入次数と出次数がともに1であることに同値。

したがって、頂点を二倍にして二部グラフを作り、
i番目の頂点とj番目の頂点が隣接するとき、
xiからy+jに、流量1、コストが元々その向きの矢印があるなら0、そうでないなら1の辺をはってやる。
このグラフ上で最小費用流を求めると、そのコストが求めるコストである。

多分最小費用循環流を求めてもできる。

ソースコード

class DirectionBoard {
	public:
	int getMinimum(vector <string> board) {
		const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0 , 1};
		const char *dir = "ULDR";
		
		int h = board.size(), w = board[0].size();
		int s = 2 * h * w, t = 2 * h * w + 1;
		costflowGraph<int> g(2 * h * w + 2);
		rep(i, h) rep(j, w) rep(d, 4){
			int y = (i + dy[d] + h) % h, x = (j + dx[d] + w) % w;
			int dd = 0;
			rep(k, 4) if(board[i][j] == dir[k]) dd = k;
			g.add(i * w + j, h * w + y * w + x, 1, dd != d);
		}
		rep(i, h) rep(j, w){
			g.add(s, i * w + j, 1, 0);
			g.add(h * w + i * w + j, t, 1, 0);
		}
		return g.min_cost_flow(s, t, h * w);
	}
};