SRM 385 500pt: TurningMaze

問題概要

W*H(W,H<=7)の盤面があり、各マスは、1.全方向通行可能、2.全方向通行不可能、3.水平方向通行可能、4.垂直方向通行可能のいずれかである。今いるマスと行く先のマスの両方が通行可能であるときのみ、マスを移動することができる。1マス移動するのと同じだけのコストを払うことにより、今いる列と行の全ての3と4が入れ替わる。ただし今いるマスは相殺し合って入れ替わらない。

考えたこと

• 最初は行も入れ替わることに気付かずに、状態数が減らせなくて困った
  • せめて今いるマスも一緒に入れ替わるなら簡単なのに…とか思っていた
• 行と列がともに入れ替わるなら今いるマスが入れ替わらないというのは非常に自然だ。これは簡単に解けそう。
• (どの列が入れ替わった状態になっているか、どの行が入れ替わった状態になっているか、今どこにいるか)を状態にして最短経路を求めるだけ。
• 書くのに時間がかかったけど無事通った。

practiceで通ったコード

計算量O( (W*H)^2*2^H*2^W * log (W+H) )位？状態数が多いのでlogが無視できない。

#include <vector>
#include <string>
#include <queue>
using namespace std;

const int MAX_W = 7;
const int dy[] = {1,-1,0,0};
const int dx[] = {0,0,1,-1};

int dist[MAX_W][MAX_W][1<<MAX_W][1<<MAX_W];
bool visited[MAX_W][MAX_W][1<<MAX_W][1<<MAX_W];

struct state{
	int dist, y, x, y_bit, x_bit;
};

bool operator<(const state& lhs, const state& rhs){
	return lhs.dist > rhs.dist;
}

struct TurningMaze {

	int minTime(vector <string> maze) {
		int H = maze.size(), W = maze[0].length();

		priority_queue<state> que;
		que.push((state){0, 0, 0, 0, 0});

		while(!que.empty()){
			state tp = que.top(); que.pop();
			if(tp.y == H - 1 && tp.x == W - 1){
				return tp.dist;
			}
			if(visited[tp.y][tp.x][tp.y_bit][tp.x_bit]){
				continue;
			}
			visited[tp.y][tp.x][tp.y_bit][tp.x_bit] = true;
			dist[tp.y][tp.x][tp.y_bit][tp.x_bit] = tp.dist;

			//遷移
			for(int rot=0; rot<2; rot++){ //回転無し：rot==0, 回転あり :rot==1
				for(int k=0; k<4; k++){
					int ny = tp.y + dy[k], nx = tp.x + dx[k];
					if(0<=ny && ny<H && 0<=nx && nx<W && !visited[ny][nx][tp.y_bit][tp.x_bit]){
						char cur = maze[tp.y][tp.x], tar = maze[ny][nx];
						bool cur_change = ( (tp.y_bit>>tp.y) ^ (tp.x_bit>>tp.x) )&1;
						bool tar_change = ( (tp.y_bit>>ny) ^ (tp.x_bit>>nx) )&1;
						bool cur_hor = cur=='A' || (cur=='D' && !cur_change) || (cur=='C' && cur_change);
						bool cur_ver = cur=='A' || (cur=='D' && cur_change)  || (cur=='C' && !cur_change);
						bool tar_hor = tar=='A' || (tar=='D' && !tar_change) || (tar=='C' && tar_change);
						bool tar_ver = tar=='A' || (tar=='D' && tar_change)  || (tar=='C' && !tar_change);

						if( (k < 2 && cur_ver && tar_ver) || (k>=2 && cur_hor && tar_hor) ){
							que.push( (state){tp.dist+1+rot, ny, nx, tp.y_bit, tp.x_bit} );
						}
					}
				}
				tp.y_bit ^= (1<<tp.y);
				tp.x_bit ^= (1<<tp.x);
			}
		}

		return -1;
	}

};