П'ятнашки#3669

П'ятнашки

1 секунда

256 мегабайтів

Дуже складна

П'ятнашки — це популярна головоломка, створена в $1878$ році Ноєм Чепменом. Вона складається з набору однакових квадратних плиток з числами, розміщених у квадратній коробці. Довжина коробки в чотири рази більша за довжину сторони плиток, тому в коробці залишається одне порожнє квадратне поле. Мета гри — переміщуючи плитки всередині коробки, досягти їх впорядкування за номерами, як показано на наступному зображенні.

Допустимі ходи можна описати як переміщення порожньої клітинки: її можна перемістити вправо ("R"), вліво ("L"), вгору ("U") або вниз ("D"), змінюючи місцями з сусідньою плиткою у відповідному напрямку.

Вам потрібно, виходячи з початкового стану головоломки, визначити найкоротшу послідовність ходів, яка приведе до впорядкованого стану.

Вхідні дані

Вхідний файл складається з $4$ рядків. У кожному рядку записано по $4$ числа від $0$ до $15$ , які представляють номери плиток у відповідних клітинках початкового стану головоломки ( $0$ відповідає порожній клітинці). Кожне з чисел зустрічається лише один раз.

Вихідні дані

У вихідний файл потрібно вивести один рядок. Якщо для заданого стану немає розв'язку, виведіть "NO SOLUTION". Якщо розв'язок існує, цей рядок повинен містити найкоротшу послідовність ходів, яка приводить головоломку до потрібного фінального стану. Якщо довжина оптимальної послідовності перевищує $45$ ходів, виведіть замість неї рядок "TOO LONG".

Приклади

Приклад 1