Задача 244
Пятнашки
Наверняка вам знакома игра пятнашки. Вместо пронумерованных плиток, мы воспользуемся семью красными плитками и восемью синими.
Ходы обозначаются заглавной начальной буквой направления (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 является ASCII-кодом k-той буквы в последовательности переходов.
Соответствующие ASCII-коды направлений:
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007
| L | 76 |
| R | 82 |
| U | 85 |
| D | 68 |
Для приведенной выше последовательности LULUR контрольная сумма составит 19761398.
А теперь, начав с конфигурации (S), найдите все кратчайшие пути к конфигурации (T).
| (S) | | , (T) |  |
Чему равна сумма всех контрольных сумм для кратчайших путей?
© Проект Эйлера | Translated problems from ProjectEuler.net