Honeycomb Walk 解説

問題名：Honeycomb Walk (PKU)
出典：Problem I, ACM/ICPC Nordic Collegiate Programming Contest 2006 (NCPC 2006), 2006-09-30
難易度：☆☆☆
問題の種類：DP, Hex
解法：メモ化探索
解答ソースコード：
- 3036-deq.cpp

典型的なDP問題です。盤が六角形のHex（ヘックス）座標なので慣れていないとコーディングがちょっとややこしい。

ステップ数が n = 14 なので，全探索をすれば 6¹⁴ 通りになって計算できません。ですが，全探索でも一度計算した値を覚えておくようにすると解けてしまいます。この問題の場合，再帰関数に渡す引数は

の3つなので，メモするのもその3種類になります。

n=14で原点に戻ってこないといけないので，x, yの最大値は7になります（8になると戻ってこれないので探索を打ち切る）。ですから，n×x×y = 14×7×7 = 686 回計算すれば解答できます。メモリも間違いなく足ります。

戻ってこれなくなったら，つまり原点を (x=0, y=0)，残りステップ数をnとすると max { |x|, |y| } > n となれば探索を打ち切りましょう。それ以外は通常の全探索です。

慣れていないとHex座標の実装に戸惑うかもしれません。 Hex座標は2次元の座標系なので (x, y) で一マスを表現できます。 (x, y) から1ステップで行ける，つまり (x, y) に隣り合ったマス目は次の図のように6種類あります。

4方向だけの格子状の盤と比較すると，Hex盤はy軸に関しては同じですが，x軸は斜めになっています（これ以外にもHex座標の表し方は色々考えられますが，これが一番簡潔な表現でしょう）。結局のところ，ループを回すための配列は

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

となります。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $

deq notes