题目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):

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).

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

题目：

你可能听说过十五数码游戏。在这里，我们用 7 个红色的棋子和 8 个蓝色的棋子，而不是用数字棋子。

一次移动由棋子滑动方向的首位大写字母指出（左 Left, 右 Right, 上 Up, 下 Down）, e.g. 从状态 (S) 开始，通过序列 LULUR 我们得到状态 (E)：

       
对于每个序列，它的校验和由以下的伪代码计算：

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

其中 m_k 为序列第 k 个字母的 ASCII 值。字母的 ASCII 值对应表如下：

L	76
R	82
U	85
D	68

对于上面给出的序列 LULUR , 其校验和为 19761398。

现在，从状态 (S) 出发，找出到达状态 (T) 的所有最短序列。

以上所有最短序列的校验和之和为多少？