yukicoder : No.1572 XI

こちらは実装の手間はともかく、方針は立てやすそう。
https://yukicoder.me/problems/no/1572

問題

H*Wのグリッドが与えられる。
一部のマスは侵入不可である。

今セル(Sy,Sx)に1面のサイズがセルと同じさいころが置いてあり、1の目が上になっている。
このさいころをセルに沿って転がし、(Gy,Gx)に1の目が上になっている状態に遷移できるか判定せよ。
また、最小の転がす回数を求めよ。

解法

現在地と1の目の状態をもってBFSすればよい。

int H,W;
int SY,SX,GY,GX;
string S[1010];
int D[1010][1010][6];

int dy[4]={0,-1,0,1};
int dx[4]={-1,0,1,0};
int to[4][6]={
	{1,5,2,0,4,3}, //l
	{4,1,0,3,5,2}, //u
	{3,0,2,5,4,1}, //r
	{2,1,5,3,0,4}, //d
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	cin>>SY>>SX;
	cin>>GY>>GX;
	SY--,SX--,GY--,GX--;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) FOR(i,6) D[y][x][i]=1<<30;
	queue<int> Q;
	D[SY][SX][0]=0;
	Q.push(SY*1000+SX);
	while(Q.size()) {
		int cy=Q.front()%1000000/1000;
		int cx=Q.front()%1000;
		int ct=Q.front()/1000000;
		Q.pop();
		if(cy==GY&&cx==GX&&ct==0) {
			cout<<D[cy][cx][ct]<<endl;
			return;
		}
		FOR(i,4) {
			int ty=cy+dy[i];
			int tx=cx+dx[i];
			int tt=to[i][ct];
			if(ty<0||ty>=H||tx<0||tx>=W||S[ty][tx]=='#') continue;
			if(D[ty][tx][tt]>D[cy][cx][ct]+1) {
				D[ty][tx][tt]=D[cy][cx][ct]+1;
				Q.push(ty*1000+tx+tt*1000000);
			}
			
			
		}
	}
	cout<<-1<<endl;
}

まとめ

さいころの転がし方の状態遷移を書いたの、初めてかも。