Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Рекурсивный DFS

Дана матрица N (1 <= N <= 100) на M (1 <= M <= 100). В матрице имеются ‘.’ – пустые клетки и ‘#’ – клетки, которые нельзя посетить. Ходить можно только вверх, вниз, влево и вправо. Дано q запросов: номер строки и номер столбца, если эта клетка – ‘#’, то она станет ‘.’, иначе – ‘#’. Для каждого из q запросов определить, достижима ли из клетки Sx;Sy клетка tx;ty. Вывести на каждой строчке “Yes”, если достижима, и “No” - иначе. Гарантируется, что клетка Sx; Sy и клетка tx; ty не являются ‘#’ клеткой в каждом запросе.
Входные данные.
На первой строчке вводятся числа S_x (1 <= Sx <= 100), S_y (1 <= Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100) и q (1 <= q <= 100). На следующих N строках дается матрица, где ‘.’ – пустая клетка и ‘#’ – клетка, которую нельзя посетить. На следующих q строках дан номер строки и номер столбца, которые надо изменить.

Выходные данные.
Вывести на каждый из q запросов “Yes”, если из клетки Sx; Sy в клетку tx; ty можно попасть, “No” – иначе.
 
Ввод Вывод
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2
No
Yes

Пояснение:
После первого запроса матрица будет такой:
.  .  #
# # .
# # #
Из точки 1;1 в 2;3 нет прохода, следовательно, выводим “No”.

После второго запроса матрица будет такой:
.  .  #
# .  .
# # #
Из точки 1;1 в 2;3 есть проход, следовательно, выводим “Yes”. Выделен путь, по которому мы сможем идти.

(с) Всеволод Шалдин
 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: