Problem
N (1 <= N <= 100) × M (1 <= M <= 100) の行列を考える。マトリックスには「.」が含まれています。 –空のセルと「#」 –訪問できない細胞。上下左右にしか移動できません。 q 個のクエリが与えられた場合: 行番号と列番号、このセルの場合 – ‘#’ の場合は ‘.’ になり、それ以外の場合は – ‘#’。 q 個のクエリのそれぞれについて、セル tx;ty がセル Sx;Sy から到達可能かどうかを判断します> .到達可能な場合は「はい」、「いいえ」の場合は各行に出力されます。 - さもないと。セル Sx が保証されます。 Sy とセル tx; ty は ‘#’ ではありません。各リクエストのセル
入力データ。
最初の行に、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 行は、変更する行番号と列番号を示します。
出力。
セル Sx からの場合、q 個のクエリのそれぞれについて出力 “Yes”; Sy をセル tx に。 ty をヒットできます。「いいえ」; –そうでなければ。
<本体>
| 入力 |
出力 |
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2 |
いいえ
はい |
説明:
最初のリクエストの後、マトリックスは次のようになります:
. . #
# # .
###
ポイント 1;1 から 2;3 への通過がないため、「No」と出力します。
2 番目のリクエストの後、マトリックスは次のようになります。
. . #
# . .
###
ポイント 1;1 から 2;3 までの通過があるので、「Yes」を出力します。私たちがたどることができる道が強調されています。
(с) Vsevolod Shaldin