Задача 244
Пятнашки

Наверняка вам знакома игра пятнашки. Вместо пронумерованных плиток, мы воспользуемся семью красными плитками и восемью синими.

Ходы обозначаются заглавной начальной буквой направления (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
где mk является ASCII-кодом k-той буквы в последовательности переходов. Соответствующие ASCII-коды направлений:
L76
R82
U85
D68

Для приведенной выше последовательности LULUR контрольная сумма составит 19761398.

А теперь, начав с конфигурации (S), найдите все кратчайшие пути к конфигурации (T).

(S), (T)

Чему равна сумма всех контрольных сумм для кратчайших путей?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net