Гном у замку
У прямокутній матриці розміром 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, якщо гном не може виконати завдання.