e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Гном в замке

Гном в замке

В прямоугольной матрице размером N×M клеток закодирован план староинного замка. Каждая клетка плана описана одним целым числом A (0A 31), образованным суммой чисел по такому правилу:

  • 1 – если есть стена на западе;
  • 2 – если есть стена на севере;
  • 4 – если есть стена на востокеі;
  • 8 – если есть стена на юге;
  • 16 - если в клетке есть мешок золота.

Считается, что внутренняя стена принадлежит двум клеткам. Например, южная стена клетки (1, 2) есть также северной стеной клктки (2, 2) (см. рисуннок и пример входного файла).

Внешняя клетка, не имеющая соответствующей внешней стены называется клеткой-выход. На рисунке изображено две такие клетки (2, 1) и (1, 5). Всего таких клеток не более 10.

В клетке с известными координатами (i, j) находится гном. Он может двигаться по соседних клетках, сделав шаг через общую сторону, если ему не мешают стены замка. За какое минимальное количество шагов K гном сможет попасть в любую клетку–выход, прихватив ровно один мешок золота (больше он не донесёт)?

prb2799-en

Входные данные

В первой строке четыре числа: N, M – размер матрицы (1 N,M 50) и i, j – координаты гнома (1 i N, 1 j M). Последующие N строк по M чисел в кождой описывают план замка за указанными выше правилам.

Выходные данные

Одно число – минимальное количество шаговK к выходу или -1, если гном не сможет выполнить задание.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 5 2 3
19 10 6 11 2
8 6 9 6 5
11 8 10 8 28
Output example #1
4
Source Stage III All-Ukrainian School Olympiad 2011-2012, Round 2, Zhytomyr