Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Игра - 4

(Время: 1 сек. Память: 32 Мб Сложность: 52%)

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
17 7
4 4
1111011
1111101
0111111
1111111
1011111
0011111
1111111
4
23 3
2 2
000
010
000
No solution

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru