EduBrick

K. Лабиринт до клетки

2000 мс · 256 МБ · всё или ничего

Тот же игрушечный лабиринт с наклонами, но отверстий в нём нет, а надо привести шарик в заданную клетку. Шарик должен в ней остановиться, а не просто прокатиться мимо.

Найдите наименьшее число наклонов.

Формат ввода

Первая строка содержит числа NN и MM (1≤N,M≤1001 \le N, M \le 100), затем координаты целевой клетки rr и cc (нумерация с единицы).

Далее идут NN строк по MM чисел: 0 — свободно, 1 — препятствие. Левый верхний угол и целевая клетка свободны.

Формат вывода

Одно число — наименьшее количество наклонов или −1-1.

Примеры

ввод
3 3 3 3
0 0 0
0 1 0
0 0 0
вывод
2
ввод
1 3 1 2
0 0 0
вывод
-1
Войдите, чтобы отправлять решения.