244 : スライダー

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

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

(S)

(E)

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

checksum = 0 checksum = (checksum × 243 + $m_1$) mod 100 000 007 checksum = (checksum × 243 + $m_2$) mod 100 000 007 … checksum = (checksum × 243 + $m_n$) mod 100 000 007

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

文字	アスキーコード
L	76
R	82
U	85
D	68

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

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

(S)

(T)

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