Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

SRM 385 TurningMaze

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

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

  • 方針を検討
    • 制約甘い・・・またbitDPか
    • どの行と列が反転してるかのフラグを持ちながらダイクストラすればよさそうだ
      • 状態数は 2^14 * 7 * 7
    • 今いる位置(nx, ny, 0-indexed)で反転操作を行うと、nx桁目とny+7桁目のbitを入れ替える
    • 今いる位置が反転してるかどうかは、nx桁目とny+7桁目のXORをとって確認する
  • 実装
    • 重い・・・
    • 各部屋の状態について、ドアが使えるかどうか配列を用意するなど工夫した
  • 最後のサンプルだけが通らない 正解「6」に対して「4」を返した
    • 手で確認してみる
    • あれ、これ4手(下、右、右、下)でいけるのでは・・・
  • 問題を読みなおす
    • そうか、ドアがつながってなきゃ通れないのか
      • 南に行くときは南の部屋の北のドアがないと通れない
  • 行き先のドアについても調べる実装を追加
    • サンプル通った。
  • 念のため最大ケース(7x7, ABCDランダム)で確認
    • TCサーバで0.4s 大丈夫だろう。
  • 提出
  • editorial曰くただのBFSで通るらしい
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class TurningMaze {
	
	public int[] dx = {1, 0, -1, 0};
	public int[] dy = {0, 1, 0, -1};
	
	public int[][] mask = {
		{0, 0, 0, 0},
		{1, 1, 1, 1},
		{0, 0, 0, 0},
		{0, 1, 0, 1},
		{1, 0, 1, 0},		
	};
	
	public int[][] rotate = {
		{0, 0},
		{1, 1},
		{2, 2},
		{3, 4},
		{4, 3}
	};
	
	class State {
		int ptn;
		int nx, ny;
		int time;
		State(int x, int y, int p, int t) {
			ptn = p;
			nx = x;
			ny = y;
			time = t;
		}
	}
	
	public int minTime(String[] maze) {
		int w = maze[0].length();
		int h = maze.length;
		int[][] data = new int[9][9];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				data[i+1][j+1] = (maze[i].charAt(j) - 'A') + 1; 
			}
		}
		
		int[][][] dp = new int[9][9][1<<14];
		
		for (int i = 0 ; i < 9 ; i++) {
			for (int j = 0 ; j < 9 ; j++) {
				Arrays.fill(dp[i][j], Integer.MAX_VALUE);
			}
		}
		dp[1][1][0] = 0;
		Queue<State> q = new PriorityQueue<State>(10000, new Comparator<State>(){
			public int compare(State a, State b) {
				return a.time - b.time;
			}
		});
		q.add(new State(1, 1, 0, 0));
		while (q.size() >= 1) {
			State stat = q.poll();
			boolean ptna = ((stat.ptn & (1<<(stat.nx-1))) >= 1);
			boolean ptnb = ((stat.ptn & (1<<(stat.ny-1 + 7))) >= 1);
			int flg = (ptna ^ ptnb) ? 1 : 0;
			int nowdoor = rotate[data[stat.ny][stat.nx]][flg];
			if (nowdoor == 0) {
				continue;
			}
			
			// go
			for (int d = 0 ; d < 4 ; d++) {
				if (mask[nowdoor][d] == 1) {
					int tx = stat.nx + dx[d];
					int ty = stat.ny + dy[d];
					boolean ptnc = ((stat.ptn & (1<<(tx-1))) >= 1);
					boolean ptnd = ((stat.ptn & (1<<(ty-1 + 7))) >= 1);
					int flgya = (ptnc ^ ptnd) ? 1 : 0;
					int doorya = rotate[data[ty][tx]][flgya];
					if (mask[doorya][(d+2)%4] == 1) {
						int nptn = stat.ptn;
						int wtime = stat.time + 1;
						if (dp[ty][tx][nptn] > wtime) {
							dp[ty][tx][nptn] = wtime;
							q.add(new State(tx, ty, nptn, wtime));
						}
					}
				}
			}
			
			// rotate
			int zptn = stat.ptn;
			int wtime = stat.time + 1;
			zptn += (1<<(stat.nx-1)) * (ptna ? -1 : 1);
			zptn += (1<<(stat.ny-1+7)) * (ptnb ? -1 : 1);
			
			
			if (dp[stat.ny][stat.nx][zptn] > wtime) {
				dp[stat.ny][stat.nx][zptn] = wtime;
				q.add(new State(stat.nx, stat.ny, zptn, wtime));
			}
		}
		
		int mintime = Integer.MAX_VALUE;
		for (int p = 0 ; p < (1<<14) ; p++) {
			mintime = Math.min(mintime, dp[h][w][p]);
		}	
		return (mintime == Integer.MAX_VALUE) ? -1 : mintime;
	}
}