Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Дана матрица 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”. Выделен путь, по которому мы сможем идти.
(с) Всеволод Шалдин