Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-09SRM383,384,385 (Practice)

SRM 383 FloorBoards

|  SRM 383 FloorBoards - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 383 FloorBoards - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8397

  • 既視感がある問題。
  • 方針を検討
    • 解説ではO((2^W)^2 * H)の動的計画法(ループ)で解いてるが、今回はメモ化再帰で解いてみよう
    • dfs(i, j, ptn) i行目j列目において、直前W個の縦横線のパターンptnについて考える
      • 縦棒を使うか横棒を使うかという選択は直前W個さえ知ってれば十分
      • 計算量 O(W*H*(2^W))
  • 実装
  • サンプル全然合わない。なぜだー
    • 次の状態を見る時 dfs(i, j+1, ptn*2) ではなく dfs(i+1, j, ptn*2)としてた・・・
    • その他にもいろいろ間違ってた
  • サンプル通った。最大ケース確認して提出
    • 見たことある問題の割に解くのが遅い・・・
import java.util.Arrays;

public class FloorBoards {

	char[][] r;
	int[][][] memo;
	int h;
	int w;
	int wptn;
	
	public int dfs(int i, int j, int ptn) {
		if (i >= h) {
			return 0;
		}
		if (j >= w) {
			return dfs(i+1, 0, ptn);
		}
		if (memo[i][j][ptn] != Integer.MAX_VALUE) {
			return memo[i][j][ptn];
		}
		
		int ans = Integer.MAX_VALUE;
		if (r[i][j] == '#') {
			ans = dfs(i, j+1, (ptn*2) & wptn);
		} else {
			int vertical = 0;
			if (i == 0 || r[i-1][j] == '#' || (ptn & (1<<(w-1))) >= 1) {
				vertical = 1;
			}
			
			int holizonal = 0;
			if (j == 0 || r[i][j-1] == '#' || (ptn & 1) == 0) {
				holizonal = 1;
			}

			ans = Math.min(ans, dfs(i, j+1, (ptn*2) & wptn) + vertical);
			ans = Math.min(ans, dfs(i, j+1, (ptn*2+1) & wptn) + holizonal);
		}
		memo[i][j][ptn] = ans;
		return ans;
	}
	
	public int layout(String[] room) {
		h = room.length;
		w = room[0].length();
		
		r = new char[h][w];
		for (int i = 0 ; i < h ; i++) {
			r[i] = room[i].toCharArray();
		}
		
		memo = new int[h][w][1<<w];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				Arrays.fill(memo[i][j], Integer.MAX_VALUE);
			}
		}
		wptn = (1<<w)-1;
		return dfs(0, 0, wptn);
	}
}