Решите головоломку
Дан квадрат размером с числами 1, 2, 3, …, 9. Требуется выполнить последовательность операций обмена, чтобы получить сетку в виде:
При каждом ходе вы можете поменять местами две соседние клетки (соседние по горизонтали или вертикали). Какое минимальное количество ходов нужно совершить, чтобы получить требуемую конфигурацию?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Входные данные
Программа получает на вход 3 строки, каждая из которых содержит 3 числа, задающие исходную сетку.
Выходные данные
Программа должна вывести минимальное количество ходов, необходимых для получения сетки 1, 2, 3, …, 9.
Примеры
Входные данные | Выходные данные |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB