Problem 244 のバックアップ(No.1)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
Problem 244 へ行く。
- 1 (2009-05-09 (土) 23:52:22)
- 2 (2009-05-10 (日) 21:37:54)
- 3 (2010-03-03 (水) 02:21:19)
- 4 (2010-03-03 (水) 02:21:19)

Problem 244 †

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

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

(S)

(E)

各経路は、擬似コードによってチェックサムが計算される:

checksum = 0
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007

mk は移動の文字列の k 番目の文字のアスキーコードの値である。アスキーコードは以下の通り:

L	76
R	82
U	85
D	68

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

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

(S)

(T)

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