---

Problem 244

---

Sliders

You probably know the game Fifteen Puzzle. Here, instead of numbered tiles, we have seven red tiles and eight blue tiles.

A move is denoted by the uppercase initial of the direction (Left, Right, Up, Down) in which the tile is slid, e.g. starting from configuration (S), by the sequence LULUR we reach the configuration (E):

(S) (E)

For each path, its checksum is calculated by (pseudocode):

checksum = 0
checksum = (checksum × 243 + m₁) mod 100 000 007
checksum = (checksum × 243 + m₂) mod 100 000 007
   …
checksum = (checksum × 243 + m_n) mod 100 000 007

where m_k is the ASCII value of the k^th letter in the move sequence and the ASCII values for the moves are:

L	76
R	82
U	85
D	68

For the sequence LULUR given above, the checksum would be 19761398.

Now, starting from configuration (S), find all shortest ways to reach configuration (T).

(S) (T)

What is the sum of all checksums for the paths having the minimal length?

---

滑块

你可能知道十五滑块谜题这个游戏。现在，我们用7块红色滑块和8块蓝色滑块取代了原来标有数字的滑块。

我们用被滑动的滑块所滑的方向对应英文单词（左=left=L，右=right=R，上=up=U，下=down=D）的首字母记录每一步，例如，从布局(S)出发，经过滑动序列LULUR，我们得到了布局(E)：

(S) (E)

对于每一步，我们按如下方式（伪代码）计算其校验和：

checksum = 0
checksum = (checksum × 243 + m₁) mod 100 000 007
checksum = (checksum × 243 + m₂) mod 100 000 007
   …
checksum = (checksum × 243 + m_n) mod 100 000 007

其中m_k是滑动序列中第k^th个字母的ASCII码，具体数值如下：

L	76
R	82
U	85
D	68

对于上述滑动序列LULUR，校验和为19761398。

现在，找出所有从布局(S)出发得到布局(T)的最短序列。

(S) (T)

所有这些最短序列的校验和之和是多少？

---