Given a matrix of N (1 <= N <= 100) by M (1 <= M <= 100). The matrix contains ‘.’ – empty cells and ‘#’ – cells that cannot be visited. You can only move up, down, left and right. Given q queries: row number and column number, if this cell – ‘#’, then it becomes ‘.’, otherwise – ‘#’. For each of q queries, determine whether cell tx;ty is reachable from cell Sx;Sy . Output on each line “Yes”, if reachable, and “No” - otherwise. It is guaranteed that the cell Sx; Sy and cell tx; ty are not ‘#’ cell in each request.
Input data.
On the first line enter the numbers Sx (1 <= Sx <= 100), Sy (1 < = Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100) and q (1 <= q <= 100). The next N lines give a matrix where ‘.’ – empty cell and ‘#’ – a cell that cannot be visited. The next q lines give the row number and column number to be changed.
Output.
Print for each of the q queries “Yes”, if from cell Sx; Sy into cell tx; ty can be hit, “No” – otherwise.
| Input |
Output |
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2 |
No
Yes |
Explanation:
After the first request, the matrix will look like this:
. . #
# # .
###
There is no passage from point 1;1 to 2;3, therefore, we print “No”.
After the second request, the matrix will look like this:
. . #
# . .
###
There is a passage from point 1;1 to 2;3, so we output “Yes”. The path we can follow is highlighted.
(с) Vsevolod Shaldin