*[[Problem 244:http://projecteuler.net/problem=244]] 「スライダー」 [#gafe3888]

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

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

CENTER:(''S'')
&ref(http://projecteuler.net/project/images/p_244_start.gif,nolink); ,
(''E'')
&ref(http://projecteuler.net/project/images/p_244_example.gif,nolink);

各経路は, 以下に示す擬似コードによってチェックサムが計算される:
>>> 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'') に到達する最短の経路を全て求めよ.

CENTER:(''S'')
&ref(http://projecteuler.net/project/images/p244_start.gif,nolink); ,
(''T'')
&ref(http://projecteuler.net/project/images/p244_target.gif,nolink);


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


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