Codeforces #676 Div2 D. Hexagons

この回は不参加だった。
http://codeforces.com/contest/1421/problem/D

問題

ヘックス状のグリッドがある。
6方向それぞれ1マス移動するコストと、目的地となるマス目の座標が与えられる。
原点から目的地に移動する最小コストを求めよ。

解法

ヘックス状のグリッドであっても、結局2つの座標軸で各セルが表現できる点で、通常のスクエア状のグリッドは変わらない。
そこで、まずスクエア状のグリッドとみなし、8方向の最小移動コストを求めよう。
あとは、極力斜め移動を使って目的地に移動しよう。
その際は、X座標が合うところまで斜め移動して縦移動するか、Y座標が合うところまで斜め移動して横移動するか、両方試そう。

int T;
ll X,Y;
ll C[6];
ll pat[3][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>Y;
		FOR(i,6) cin>>C[i];
		FOR(x,3) FOR(y,3) pat[x][y]=1LL<<60;
		pat[2][2]=C[0];
		pat[1][2]=C[1];
		pat[0][1]=C[2];
		pat[0][0]=C[3];
		pat[1][0]=C[4];
		pat[2][1]=C[5];
		int x2,y2;
		FOR(i,8) {
			for(x=-1;x<=1;x++) for(y=-1;y<=1;y++) {
				for(x2=-1;x2<=1;x2++) for(y2=-1;y2<=1;y2++) {
					int tx=x+x2;
					int ty=y+y2;
					if(abs(tx)>=2) continue;
					if(abs(ty)>=2) continue;
					pat[1+tx][1+ty]=min(pat[1+tx][1+ty],pat[1+x][1+y]+pat[1+x2][1+y2]);
				}
			}
		}
		if(X<0) {
			FOR(y,3) swap(pat[2][y],pat[0][y]);
			X=-X;
		}
		if(Y<0) {
			FOR(x,3) swap(pat[x][2],pat[x][0]);
			Y=-Y;
		}
		ll ret=X*pat[2][1]+Y*pat[1][2];
		if(X<=Y) {
			// move X
			ret=min(ret,X*pat[2][2]+(Y-X)*pat[1][2]);
			// move Y
			ret=min(ret,Y*pat[2][2]+(Y-X)*pat[0][1]);
		}
		else {
			// move X
			ret=min(ret,X*pat[2][2]+(X-Y)*pat[1][0]);
			// move Y
			ret=min(ret,Y*pat[2][2]+(X-Y)*pat[2][1]);
		}
		cout<<ret<<endl;
		
		
		
	}
}

まとめ

Div2Dにしては簡単。