*[[Problem 244:http://projecteuler.net/index.php?section=problems&id=244]] [#gafe3888]

おそらく'''15パズル'''はご存知だろう。ここでは、数字の書かれたタイルの代わりに、7枚の赤いタイルと8枚の青いタイルを使用する。

移動は、タイルの動いた方向(Left, Right, Up, Down)の大文字のイニシャルで表す。
すなわち、最初の状態(''S'')から文字列 ''LULUR'' を経て状態(''E'')にたどり着く。

(S)
#ref(http://projecteuler.net/project/images/p_244_start.gif)
(E)
#ref(http://projecteuler.net/project/images/p_244_example.gif)

各経路は、擬似コードによってチェックサムが計算される:
>>> checksum = 0~
checksum = (checksum × 243 + m&sub{1};) mod 100 000 007~
checksum = (checksum × 243 + m&sub{2};) mod 100 000 007~
…~
checksum = (checksum × 243 + m&sub{n};) mod 100 000 007

m&sub{k}; は移動の文字列の k 番目の文字のアスキーコードの値である。アスキーコードは以下の通り:

|''L''|76|
|''R''|82|
|''U''|85|
|''D''|68|

上で例に挙げた文字列 ''LULUR'' の場合、チェックサムは 19761398 になるだろう。

では、状態(''S'')から始めて、状態(''T'')に到達する最短の経路を全て求めよ。

(S)
#ref(http://projecteuler.net/project/images/p_244_start.gif)
(T)
#ref(http://projecteuler.net/project/images/p_244_target.gif)


最小の長さとなる経路のチェックサム全ての合計を求めよ。


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS