AOJ 1290,PKU 3945 Traveling Cube

問題概要

NxMのマス目を色のついたサイコロを転がすことを考える．
マス目にも色が付いていて，黒の場合はサイコロが乗ることは出来ず，白の場合はサイコロは自由に乗ることが出来る．それ以外の色の場合はサイコロの上面の色とマス目の色は一致しないといけないとする．
マス目の色を辿る順序が与えられるので，最小の転がす回数を求めよ．
ただし，白以外の色に対して同じ色のマスに二度立ちいることは禁じられている．

解法

BFSする

実装(C++)

実装問題．結構面倒．

#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
#include <cstring>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
//#include<vector>が必要
enum FACE { TOP, BOTTOM, FRONT, BACK, LEFT, RIGHT };
template <class T>
struct Dice{
public:
	Dice(){
		id[0]=TOP;id[1]=FRONT;id[2]=LEFT;id[3]=RIGHT;id[4]=BACK;id[5]=BOTTOM;
	}
	T& operator[] (FACE f){return var[id[f]];}
	const T& operator[] (FACE f)const {return var[id[f]];}
	bool operator==(const Dice<T> &a)const {
		const Dice<T> &b=*this;
		for(int i=0;i<6;i++){
			if(a[(FACE)i]!=b[(FACE)i])return false;
		}
		return true;
	}
	void roll_x(){roll(TOP,BACK,BOTTOM,FRONT);}
	void roll_y(){roll(TOP,LEFT,BOTTOM,RIGHT);}
	void roll_z(){roll(FRONT,RIGHT,BACK,LEFT);}
	void roll_rx(){rroll(TOP,BACK,BOTTOM,FRONT);}
	void roll_ry(){rroll(TOP,LEFT,BOTTOM,RIGHT);}
	void roll_rz(){rroll(FRONT,RIGHT,BACK,LEFT);}
	vector<Dice> all_rolls(){
		vector<Dice> res;
		for(int k=0;k<6;(k&1?roll_y():roll_x()),k++){
			for(int i=0;i<4;roll_z(),i++){
				res.push_back(*this);
			}
		}
		return res;
	}
	bool equivalent_to(const Dice &di){
		for(int k=0;k<6;(k&1?roll_y():roll_x()),k++){
			for(int i=0;i<4;roll_z(),i++){
				if(*this==di)return true;
			}
		}
		return false;
	}
private:
	T var[6]; //実際の値の記憶
	int id[6]; //回転などの記憶
	void roll(FACE a,FACE b,FACE c,FACE d){//a b c d →b c d a
		int tmp=id[a];
		id[a]=id[b];id[b]=id[c];id[c]=id[d];id[d]=tmp;
	}
	void rroll(FACE a,FACE b,FACE c,FACE d){
		int tmp=id[a];
		id[a]=id[d];id[d]=id[c];id[c]=id[b];id[b]=tmp;
	}
};
const string S="rcgmbywk";
int char2int[256];
void init(Dice<char> &d){
	d[TOP]='r';
	d[BOTTOM]='c';
	d[BACK]='g';
	d[FRONT]='m';
	d[RIGHT]='b';
	d[LEFT]='y';
}
int H,W;
char MAP[45][45];
string order;
struct State{
	Dice<char> dice;
	int x,y;
	int cnt;
	State(const Dice<char> &d,int x=0,int y=0,int cnt=0):dice(d),x(x),y(y),cnt(cnt){
	}
};
int turn[30][30][6][6][6][7];
#define D(dice) [char2int[(int)dice[TOP]]][char2int[(int)dice[FRONT]]][char2int[(int)dice[RIGHT]]]
int solve(int sx,int sy){
	memset(turn,0x7F,sizeof(turn));
	Dice<char> s;
	init(s);
	turn[sx][sy]D(s)[0]=0;
	queue<State> que;
	que.push(State(s,sx,sy,0));
	while(!que.empty()){
		State now=que.front();que.pop();
		//cout<<now.x<<","<<now.y<<","<<now.cnt<<":"<<now.dice[TOP]<<":"<<order[now.cnt]<<endl;
		int t=turn[now.x][now.y]D(now.dice)[now.cnt];
		if(now.cnt==6)return t;
		//右に転がる
		int nx=now.x+1,ny=now.y;
		if(nx>=0&&nx<W&&ny>=0&&ny<H){
			now.dice.roll_y();
			if(MAP[nx][ny]=='w'&&turn[nx][ny]D(now.dice)[now.cnt]>t+1){
				turn[nx][ny]D(now.dice)[now.cnt]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt));
			}else if(turn[nx][ny]D(now.dice)[now.cnt+1]>t+1&&MAP[nx][ny]==now.dice[TOP]&&MAP[nx][ny]==order[now.cnt]){
				turn[nx][ny]D(now.dice)[now.cnt+1]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt+1));
			}
			now.dice.roll_ry();
		}

		//左に転がる
		nx=now.x-1,ny=now.y;
		if(nx>=0&&nx<W&&ny>=0&&ny<H){
			now.dice.roll_ry();
			if(MAP[nx][ny]=='w'&&turn[nx][ny]D(now.dice)[now.cnt]>t+1){
				turn[nx][ny]D(now.dice)[now.cnt]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt));
			}else if(turn[nx][ny]D(now.dice)[now.cnt+1]>t+1&&MAP[nx][ny]==now.dice[TOP]&&MAP[nx][ny]==order[now.cnt]){
				turn[nx][ny]D(now.dice)[now.cnt+1]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt+1));
			}
			now.dice.roll_y();
		}

		//上に転がる
		nx=now.x,ny=now.y-1;
		if(nx>=0&&nx<W&&ny>=0&&ny<H){
			now.dice.roll_rx();
			if(MAP[nx][ny]=='w'&&turn[nx][ny]D(now.dice)[now.cnt]>t+1){
				turn[nx][ny]D(now.dice)[now.cnt]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt));
			}else if(turn[nx][ny]D(now.dice)[now.cnt+1]>t+1&&MAP[nx][ny]==now.dice[TOP]&&MAP[nx][ny]==order[now.cnt]){
				turn[nx][ny]D(now.dice)[now.cnt+1]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt+1));
			}
			now.dice.roll_x();
		}
		//下に転がる
		nx=now.x,ny=now.y+1;

		if(nx>=0&&nx<W&&ny>=0&&ny<H){
			now.dice.roll_x();
			if(MAP[nx][ny]=='w'&&turn[nx][ny]D(now.dice)[now.cnt]>t+1){
				turn[nx][ny]D(now.dice)[now.cnt]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt));
			}else if(turn[nx][ny]D(now.dice)[now.cnt+1]>t+1&&MAP[nx][ny]==now.dice[TOP]&&MAP[nx][ny]==order[now.cnt]){
				turn[nx][ny]D(now.dice)[now.cnt+1]=t+1;
				que.push(State(now.dice,nx,ny,now.cnt+1));
			}
			now.dice.roll_rx();
		}
	}
	return -1;
}
string in[45];
int main(){
	REP(i,S.size()){
		char2int[(int)S[i]]=i;
	}
	for(;cin>>W>>H;){
		if(H==0)break;
		REP(i,H)cin>>in[i];
		REP(x,W)REP(y,H){
			MAP[x][y]=in[y][x];
		}
		int sx,sy;
		REP(x,W)REP(y,H){
			if(MAP[x][y]=='#'){
				MAP[x][y]='w';
				sx=x;sy=y;
			}
		}
		cin>>order;
		int ans=solve(sx,sy);
		if(ans<0)cout<<"unreachable"<<endl;else cout<<ans<<endl;
	}

}