Вы наткнулись на новый вид шахматной головоломки. Доска, на которой вы играете, не обязательно \(8 \times 8\), но обязательно \(N \times N\). На каждой клетке записано некоторое число от \(1\) до \(N^2\), и все числа попарно различны. В \(j\)-й клетке \(i\)-й строки записано число \(A_{ij}\).
У вас в распоряжении только три фигуры: конь, слон и ладья. Вначале вы выставляете одну из фигур в клетку с номером \(1\) (вы сами выбираете какую). Далее вы хотите добраться до клетки с номером \(2\) (возможно, проходя через некоторые другие клетки в процессе), далее — до клетки \(3\) и так далее, пока не достигнете клетки \(N^2\). За один шаг вы можете либо сделать один валидный ход текущей фигурой, либо заменить фигуру на другую в вашем распоряжении. Каждая клетка может быть посещена любое количество раз.
Конь может ходить на две клетки по горизонтали и одну по вертикали, либо на две клетки по вертикали и одну по горизонтали. Слон двигается по диагонали. Ладья движется по вертикали или горизонтали. Во время хода фигуры она должна переместиться в клетку, отличную от текущей.
Вы хотите минимизировать общее количество шагов. Среди всех путей с одинаковым количеством шагов вам нужно выбрать тот, который минимизирует количество замен фигур.
Найдите путь, отвечающий всем условиям.