Магический лабиринт
Магический лабиринт представлен в виде прямоугольной таблицы размером H строк на W столбцов (0 < H < 100, 0 < W < 100). Каждая ячейка этой таблицы может содержать либо ноль, либо единицу. Нули обозначают свободные ячейки, а единицы — стены. Лабиринт называется магическим, потому что содержимое его ячеек меняется каждую секунду. В первую секунду все ячейки содержат единицы. Затем содержимое каждой ячейки меняется с периодом а: в течение первых (а–1) секунд ячейка содержит 1, в следующую секунду — 0, затем снова 1 в течение следующих (а–1) секунд, и так далее. Для каждой ячейки своё значение a (1 < a < 24).
Путь в лабиринте — это последовательность ячеек, каждая из которых содержит ноль, и каждая пара последовательных ячеек имеет общую сторону.
Необходимо определить наименьшее положительное t, при котором в t-ю секунду выполняются следующие условия:
Ячейки (1, 1) и (H, W) содержат нули.
Существует путь в лабиринте, соединяющий эти две ячейки.
Входные данные
Первая строка входного файла содержит натуральные числа H и W.
Каждая из следующих H строк содержит по W чисел: j-е число k-й строки задаёт значение а для ячейки в j-м столбце и k-й строке.
Выходные данные
Выходной файл должен содержать одно целое число — искомое t. Если такого t не существует, ответом будет число ноль.
Примечание: В примере 3 содержимое магического лабиринта меняется следующим образом: