Игра - 4

А вы играли в игру «Кота в угол»? Правила игры очень просты. Есть прямоугольное игровое поле, заполненное клетками по принципу пчелиных сот – из каждой клетки можно перейти на 6 соседних. На одной из клеток сидит кот. За один ход кот может перейти на одну из соседних клеток, если она свободна (на рисунке свободные клетки светлые, а занятые – темные). Кот хочет как можно быстрее выйти за пределы игрового поля.

Определите минимальное число ходов, за которое он сможет это сделать.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и количество клеток в строке соответственно (N, M ≤ 1000). Вторая строка содержит два натуральных числа Y, X – номер строки и номер клетки в строке, где находится кот (Y ≤ N, X ≤ M). Далее идет N строк по M символов – описание игрового поля. Свободные клетки обозначены символом «1», занятые – символом «0».

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

В выходной файл OUTPUT.TXT выведите минимальное количество ходов, за которое кот может выйти за пределы игровой области. Или «No solution» (без кавычек), если это невозможно.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]