Problem
Étant donné une matrice de N (1 <= N <= 100) par M (1 <= M <= 100). La matrice contient ‘.’ – cellules vides et ‘#’ – Cellules non visitables. Vous ne pouvez vous déplacer que vers le haut, le bas, la gauche et la droite. Étant donné q requêtes : numéro de ligne et numéro de colonne, si cette cellule – ‘#’, puis il devient ‘.’, sinon – ‘#’. Pour chacune des q requêtes, déterminez si la cellule tx;ty est accessible à partir de la cellule Sx;Sy . Afficher sur chaque ligne “Oui”, si joignable, et “Non” - sinon. Il est garanti que la cellule Sx ; Sy et cellule tx ; ty ne sont pas ‘#’ cellule dans chaque requête.
Données d'entrée.
Sur la première ligne, entrez les nombres Sx (1 <= Sx <= 100), Sy (1 < = Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100 ) et q (1 <= q <= 100). Les N lignes suivantes donnent une matrice où ‘.’ – cellule vide et ‘#’ – une cellule qui ne se visite pas. Les q lignes suivantes donnent le numéro de ligne et le numéro de colonne à modifier.
;
Sortie.
Afficher pour chacune des q requêtes “Oui”, si à partir de la cellule Sx ; Sy dans la cellule tx ; ty peut être touché, “Non” – sinon.
| Entrée |
Sortie |
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2
Non
Oui |
Explication :
Après la première requête, la matrice ressemblera à ceci :
. . #
# # .
###
Il n'y a pas de passage du point 1;1 à 2;3, donc on imprime “Non”.
Après la deuxième requête, la matrice ressemblera à ceci :
. . #
# . ; .
###
Il y a un passage du point 1;1 au point 2;3, donc nous sortons “Oui”. Le chemin que nous pouvons suivre est mis en évidence.
(с) Vsevolod Shaldin