Problem
Die Matrix N (1 <= N <= 100) ist auf M (1 <= M <= 100) gegeben. Es gibt ‘ in der Matrix.’ – leere Zellen und ‘#’ – Zellen, die nicht besucht werden können. Sie können nur nach oben, unten, links und rechts gehen. Die q-Abfrage ist gegeben: Zeilennummer und Spaltennummer, wenn diese Zelle – ‘#’ ist, wird sie ‘.’, sonst – ‘#’. Bestimmen Sie für jede der q-Abfragen, ob die Zelle Sx;Sy Zelle tx;ty erreichbar ist. Geben Sie in jeder Zeile "Yes”" aus, wenn erreichbar, und "No” - andernfalls. Es ist garantiert, dass die Zelle Sx; Sy und die Zelle tx; ty nicht die ‘#’ Zelle in jeder Abfrage ist.
Eingabe.
In der ersten Zeile werden die Zahlen Sx eingegeben (1 <= Sx <= 100), Sy (1 <= Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), ty (1 <= ty <= 100), ty (1 <= ty <=100), ty (1 <= tx <= 100), ty (1 <= ty sub> <= 100), N (1 <= N <= 100), M(1 <= M <= 100) und q (1 <= q <= 100). In den nächsten N Zeilen wird eine Matrix angegeben, wobei ‘.’ – eine leere Zelle und ein ‘#’ – Käfig, der nicht besucht werden kann. In den folgenden q Zeilen werden die Zeilennummer und die Spaltennummer angegeben, die Sie ändern möchten.
Ausgabe.
Wird für jede der q-Abfragen “Yes” ausgegeben, wenn aus der Zelle Sx; Sy in die Zelle tx; ty gelangt werden kann, “No” – andernfalls.
Eingabe |
Ausgabe |
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2 |
No
Yes |
Erklärung:
Nach der ersten Abfrage lautet die Matrix wie folgt:
. . #
# # .
# # #
Von Punkt 1;1 nach 2;3 gibt es keinen Durchgang aus, daher geben wir “No” aus.
Nach der zweiten Abfrage lautet die Matrix wie folgt:
. . #
# . .
# # #
Von Punkt 1;1 nach 2;3 gibt es eine Passage, daher geben wir “Yes” aus. Es ist ein Weg markiert, den wir gehen können.
(c) Vsevolod Shaldin