Гном в замке
В прямоугольной матрице размером N×M клеток закодирован план староинного замка. Каждая клетка плана описана одним целым числом A (0 ≤ A ≤ 31), образованным суммой чисел по такому правилу:
1 – если есть стена на западе;
2 – если есть стена на севере;
4 – если есть стена на востокеі;
8 – если есть стена на юге;
16 - если в клетке есть мешок золота.
Считается, что внутренняя стена принадлежит двум клеткам. Например, южная стена клетки (1, 2) есть также северной стеной клктки (2, 2) (см. рисуннок и пример входного файла).
Внешняя клетка, не имеющая соответствующей внешней стены называется клеткой-выход. На рисунке изображено две такие клетки (2, 1) и (1, 5). Всего таких клеток не более 10.
В клетке с известными координатами (i, j) находится гном. Он может двигаться по соседних клетках, сделав шаг через общую сторону, если ему не мешают стены замка. За какое минимальное количество шагов K гном сможет попасть в любую клетку–выход, прихватив ровно один мешок золота (больше он не донесёт)?
Входные данные
В первой строке четыре числа: N, M – размер матрицы (1 ≤ N,M ≤ 50) и i, j – координаты гнома (1 ≤ i ≤ N, 1 ≤ j ≤ M). Последующие N строк по M чисел в кождой описывают план замка за указанными выше правилам.
Выходные данные
Одно число – минимальное количество шагов K к выходу или -1, если гном не сможет выполнить задание.