CF #354(Div2) D - Theseus and labyrinth

問題 : Problem - 676D - Codeforces

概要 :
テセウスがミノタウロスを倒しに行く、その最短経路を求める。
N*Mのフィールドが与えられて、それぞれのブロックについて上下左右それぞれに扉が付いているかどうかの情報が与えられる。そして、あるブロックとその4近傍のブロックの接している辺にどちらのブロックも扉を持っていたら、それらのブロック間は移動可能。
テセウスが一回にできることは以下の二つ。
・今いるところから移動可能な隣接するブロックに移動する。
・全てのブロックを時計回りに90度回転させる

解法 :

bfs

このフィールドが取り得る状態は4つだけなので(∵4回転すれば元に戻る)ブロック全てを90度回転させたのを一つ上のフィールドとみなして、4近傍+上に登るの5方向に対してbfsを行うことで最短経路長が求まる。

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<queue>

using namespace std;


const int INF=100000000;
const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};

int id[12][4]={  //{up,right,down,left}
	{1,1,1,1},
	{0,1,0,1},
	{1,0,1,0},
	{1,0,0,0},
	{0,1,0,0},
	{0,0,0,1},
	{0,0,1,0},
	{1,1,1,0},
	{1,0,1,1},
	{0,1,1,1},
	{1,1,0,1},
	{0,0,0,0}
};
string i_str="+-|^><vLRUD*";

struct P{
	int x,y,z;
	P(int a,int b,int c):x(a),y(b),z(c){}
};

struct cell{
	int  movable[4];
	int dist;
	cell(char c){
		fill(movable,movable+4,0);
		dist=INF;
		memcpy(movable,id[i_str.find(c)],sizeof(movable));
	}
	cell(cell* c){
		dist=INF;
		for(int i=0;i<4;i++){
			movable[(i+1)%4]=c->movable[i];
		}
	}
};

cell* data [4][1002][1002];    //data[z][x][y]
int H,W;
int s_x,s_y,g_x,g_y;

bool is_movable(P from,P to,int d){
	if(data[from.z][from.x][from.y]->movable[d]==1 && data[to.z][to.x][to.y]->movable[(d+2)%4]==1){
//		cout<<"("<<from.x<<","<<from.y<<","<<from.z<<") -> ("<<to.x<<","<<to.y<<","<<to.z<<")"<<endl;
		return true;
	}
	return false;
}

void bfs(){
	queue<P> que;
	que.push(P(s_x,s_y,0));
	while(!que.empty()){
		P p=que.front();que.pop();
		for(int i=0;i<4;i++){
			int nx=p.x+dx[i],ny=p.y+dy[i];
			if(is_movable(p,P(nx,ny,p.z),i)){
				if(data[p.z][p.x][p.y]->dist+1<data[p.z][nx][ny]->dist){
					data[p.z][nx][ny]->dist=data[p.z][p.x][p.y]->dist+1;
					que.push(P(nx,ny,p.z));
				}
			}
		}
		if(data[p.z][p.x][p.y]->dist+1<data[(p.z+1)%4][p.x][p.y]->dist){
			data[(p.z+1)%4][p.x][p.y]->dist=data[p.z][p.x][p.y]->dist+1;
			que.push(P(p.x,p.y,(p.z+1)%4));
		}
	}
}

int main(){
	cin>>H>>W;
	for(int i=0;i<=1001;i++){
		for(int j=0;j<=1001;j++){
			if(i>=1 && i<=H && j>=1 && j<=W){
				char c;
				cin>>c;
				data[0][j][i]=new cell(c);
			}
			else {
				data[0][j][i]=new cell('*');
			}
		}
	}
	cin>>s_y>>s_x>>g_y>>g_x;
	data[0][s_x][s_y]->dist=0;
	for(int l=1;l<4;l++){
		for(int i=0;i<=H+1;i++){
			for(int j=0;j<=W+1;j++){
				data[l][j][i]=new cell(data[l-1][j][i]);
			}
		}
	}

	bfs();
	int ans=INF;
	for(int i=0;i<4;i++){
		ans=min(ans,data[i][g_x][g_y]->dist);
	}
	if(ans==INF)ans=-1;
	cout<<ans<<endl;
}

個人的に実装が重かった(むっちゃ時間かかった)