|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1798. Disappeared path
|
| View Problem Statistics | Submit | Problem added debug |
|
Вася – известный (в своей школе) разработчик компьютерных игр. В настоящее время он работает над программой, позволяющей создавать карты лабиринтов для очередной игры. Карта лабиринта представляет собой клетчатое поле размером N × M клеток. Вход в лабиринт находится в левой верхней клетке (с координатами 1, 1 ), выход – в правой нижней клетке (с координатами N, M ). Каждая клетка поля может быть или пустой, или закрашенной. Пустая клетка обозначает свободное место, закрашенная – непроходимую стену. Из одной пустой клетки можно перейти в другую, если они имеют общую сторону. За пределы лабиринта выходить нельзя. Программа Васи работает следующим образом. Вначале все клетки пусты. На каждом шаге он выбирает какую-то пустую клетку и щёлкает по ней мышкой, в результате клетка закрашивается. Через несколько таких шагов карта лабиринта готова. Теперь Вася хочет добавить в свою программу проверку, будет ли полученный лабиринт проходимым. Лабиринт является проходимым, если существует хотя бы один путь из левой верхней клетки в правую нижнюю. Если же пути не существует, то Вася хочет узнать номер первого шага, после которого это произошло. Помогите Васе решить данную задачу. Входные данные В первой строке входных данных записаны через пробел три числа N, M и K – размеры поля (число строк и столбцов) и количество закрашенных клеток. В следующих K строках записаны через пробел пары чисел Yi и Xi – координаты очередной закрашиваемой клетки (номер строки и номер столбца). Гарантируется, что Вася щёлкал только по пустым клеткам. Выходные данные Выведите одно число – номер первого шага, после которого лабиринт стал непроходимым. Если же лабиринт остался проходимым после всех закрашиваний, то выведите 0 (ноль). Система оценки Подзадачи: 1 ≤ N, M ≤ 20, 1 ≤ K ≤ N × M – 30 баллов, 20 < N, M ≤ 500, 1 ≤ K ≤ 100 – 30 баллов 20 < N, M ≤ 500, 100 < K ≤ N × M – 40 баллов Пример Входные данные 3 4 5 Выходные данные 4 Примечание Рисунок к примеру из условия (цифры показывают, в каком порядке закрашивались клетки): 
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | School olympiads and couses of Vologda region / | All-Russian school olympiad, municipal stage / | Municipal stage 2017-18 / | Forms 9-11 / |
| 1797. 3 - Sorting | 1798. | 1799. 5 - New year's dance |
| time generating 0.109 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |