Модуль: Поиск в глубину. DFS


Задача

8 /19


Рекурсивный DFS


Задача

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

Формат входных данных
На первой строчке вводятся числа Sx (1 <= Sx <= 100), Sy (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”, если из клетки (SxSy) в клетку (txty) можно попасть, “No” – иначе.
 
Пояснение
В тестовом примере после первого запроса матрица будет такой:
..#
##.
###
Из точки (1; 1) в (2; 3) нет прохода, следовательно, выводим “No”.

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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6442
Python141
Комментарий учителя