Игра "14"
GAME14
Описание
Задана таблица размером 4×4, в каждой клетке которой, кроме двух, содержится одно из чисел от 1 до 14 (все числа разные). Оставшиеся две клетки - пустые (пример приведен на рисунке 1). Число из любой клетки разрешено перемещать в любую пустую соседнюю клетку по горизонтали или по вертикали. Клетка, в которой ранее размещалось число, становится пустой.
| 3 | 14 | 2 | 8 |
| 5 | 11 | 13 | 4 |
| 9 | 1 | 10 | |
| 6 | 7 | 12 |
Рисунок 1
Необходимо, последовательно выполняя указанные разрешенные перемещения, преобразовать заданную таблицу в некоторое конечное состояние. В конечном состоянии пустые клетки всегда находятся в последней строке справа.
Задача
Составьте программу GAME14, которая:
Вводит начальную и конечную таблицу из текстового файла GAME14.IN
Выполняет преобразование исходной таблицы в конечную
На каждом шаге преобразования выдаёт сделанное перемещение в текстовый файл GAME14.OUT
Входной файл содержит 8 строк, в каждой из которых 4 числа, разделённых пробелами - сначала идут 4 строки исходной матрицы, затем - 4 строки конечной матрицы. Пустые клетки обозначены нулями.
В выходном файле каждая строка - это один шаг преобразования вида: x1,y1,x2,y2, где (x1,y1) - это исходное положение числа, (x2,y2) - клетка, в которую это число перемещается. Нумерация строк каждой таблицы - сверху вниз, столбцов - слева направо (1<=x1,y1,x2,y2<=4). Числа в строке разделены пробелами.
Лучшей считается та программа, которая осуществляет требуемое преобразование за меньшее число шагов.
Например:
GAME14.IN
3 14 2 8
5 11 13 4
9 1 10 0
6 0 7 12
3 14 2 8
5 11 13 4
9 1 10 7
6 12 0 0
GAME14.OUT
3 3 3 4
4 3 3 3
4 4 4 3
4 3 4 2
3 3 4 3
3 4 3 3
4 3 4 4
4 4 3 4