UAPC2010 Problem G: Rolling Dice

本番で9RE出して結局通らなかった問題。
コンストラクタをtypoしてた。ああもおお悔しいなああああああ!!!!!

サイコロの実装はかなり綺麗だと思うので参考にしたい方はどうぞ。

問題概要

将軍様が云々。

h*wマスのグリッドのそれぞれに数字が書かれている。
スタートのグリッドにサイコロが1を上に、2を南に、3を東にした状態で置かれている。

サイコロを一度転がす度に、移動先のグリッドに書かれた数字×移動後のサイコロの底面の数字のペナルティが発生する。
サイコロをグリッドにそって転がしながらゴールまで運ぶ経路のうち、ペナルティを最小にするようなものにおけるペナルティを求めよ。

サイコロはグリッドの外へ出てはいけない。

解法

サイコロの位置、向きをノードとし、出発点からの距離を今までのペナルティとしたダイクストラ法。
サイコロの向きは2面の向きを決定すれば一意に定まる。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
struct N{
	int t,b,n,s,e,w;
	int y,x;
	
	int c;
	bool operator<(const N &r)const
	{
		return c>r.c;
	}
	void roll(int d)
	{
		int tmp;
		y+=dy[d],x+=dx[d];
		
		if(d==0)
		{
			tmp=t; t=s; s=b; b=n; n=tmp;
		}else if(d==1)
		{
			tmp=t; t=e; e=b; b=w; w=tmp;
		}else if(d==2)
		{
			tmp=t; t=n; n=b; b=s; s=tmp;
		}else
		{
			tmp=t; t=w; w=b; b=e; e=tmp;
		}
	}
};

int dp[10][10][50];

int main()
{
	int h,w;
	while(cin>>h>>w,h)
	{
		int g[h][w],sy,sx,gy,gx;
		rep(i,h)rep(j,w)cin>>g[i][j];
		
		cin>>sy>>sx>>gy>>gx;
		rep(i,10)rep(j,10)fill_n(dp[i][j],50,inf);
		dp[sy][sx][1*7+2]=0;
		
		N cur; cur.y=sy,cur.x=sx,cur.c=0;
		cur.t=1,cur.b=6,cur.e=3,cur.w=4,cur.s=2,cur.n=5;
		
		
		priority_queue<N> Q; Q.push(cur);
		while(!Q.empty())
		{
			cur=Q.top(); Q.pop();
			
			if(cur.y==gy&&cur.x==gx)
			{
				cout<<cur.c<<endl; break;
			}
			
			rep(d,4)
			{
				int ny=cur.y+dy[d],nx=cur.x+dx[d];
				if(ny<0||nx<0||ny>=h||nx>=w)continue;
				
				N nxt=cur; nxt.roll(d);
				nxt.c+=g[ny][nx]*nxt.b;
				if(dp[ny][nx][nxt.t*7+nxt.s]<=nxt.c)continue;
				dp[ny][nx][nxt.t*7+nxt.s]=nxt.c;
				Q.push(nxt);
			}
		}
	}
	
	return 0;
}