В верхнем левом углу прямоугольного поля
размерами NM размещается игральний кубик,
разворот которого изображен на рисунке. Кубик ориентирован
так, что передней грани соответствует единица, а слева
находится грань, которой соответствует двойка. Клетки поля
квадратные, их размеры совпадают с размерами грани кубика.
Кубик может двигаться по полю, переворачиваясь
через одно из ребер, и попадать при этом в соседнюю снизу,
сверху, справа или слева клетку поля. Например, если из
начального состояния кубик двигается направо, то передней
станет грань с двойкой, а если вниз — то с тройкой. Кубик не
может выходить за пределы поля.
Задание
Напишите программу, которая по информации
о поле находит один из возможных путей кубика из верхнего
левого угла в нижний правый угол поля. При этом необходимо
найти такой путь, чтобы передняя грань кубика в целевой клетке
имела максимальное возможное значение. Кубик может посещать
каждую клетку поля несколько раз.
Входные данные
Первая строка содержит
два натуральных числа N и M (2≤N, M≤50), которые определяют
высоту и ширину поля соответственно. Далее задается поле,
которое представлено N строками, каждая из которых состоит из
M чисел, каждое из которых равно 0 либо 1. В случае,
когда клетке поля соответствует число 1, кубику запрещено
посещать данную клетку. В противном случае эта клетка может
встречаться в пути кубика. Начальной клетке всегда
соответствует число 0.
Выходные данные
Первая строка должна
содержать натуральное число W— длину найденого пути.
Далее в файле должны находиться W строк, каждая из
которых задает координату клетки поля на текущем шаге.
Координата представляет собой пару натуральных чисел: номер
строки и номер столбца клетки поля.
В случае, когда искомого пути не существует,
выходной файл должен содержать строку с числом -1.
Пример входных данных
Пример выходных данных
