配点 : 100 点
問題文
你正在玩滑块拼图。这个拼图使用纵向列的格子排列的棋盘。 N 行、横 N 棋盘从上到下的 i 行,从左到右的 j 列的格子是, (i, j) 。 障碍物放置在棋盘上的一些方格上。 (1 可能没有。 ) 此外,通过在该棋盘上滑动而移动的棋子是 K 行、横 K 占据该列的正方形。
该棋子可以放置在不与障碍物重叠的地方。 您可以将其沿 4 方向平移。
类似以下的查询 您将收到 Q 查询,因此请逐一处理。
- 2 两个方块
给出了 (r_1, c_1) 和 (r_2, c_2) 。作品的左上角
放置该片段的左上角,使其与 (r_1, c_1) 重叠
只要滑动就能到达与 (r_2, c_2) 重叠的状态
Yes,如果无法访问No。 我锻炼
制約
- 1 \leq N \leq 1000
- 1 \leq K \leq N
- K 是一个整数。 由
- 1 \leq Q \leq 10^5
- s_{ij} (1 \leq i, j \leq N) 为
.或#。 - 1 \leq r_{i1}, c_{i1}, r_{i2}, c_{i2} \leq N-K+1 (1 \leq i \leq Q)
- 在每个查询中, 左上角带有(r_1, c_1) 的尺寸 K \times K 方形和 (r_2, c_2) 的尺寸 K \times K 的正方形区域内没有障碍物。
入力
输入按以下格式给出。然而,s_{ij} (1 \leq i, j \leq N) 是
当 . 时,董事会的 (i, j) 上面没有放置任何障碍物。 # 当董事会
表示在 (i, j) 处放置了障碍物。
另外, r_{i1}, c_{i1}, r_{i2}, c_{i2} (1 \leq i \leq Q)分别是
由第 i 个查询给出
代表 r_1, c_1, r_2, c_2 。
N K Q
s_{11}s_{12} ... s_{1N}
:
s_{N1}s_{N2} ... s_{NN}
r_{11} c_{11} r_{12} c_{12}
:
r_{Q1} c_{Q1} r_{Q2} c_{Q2}
出力
i 行目 (1 \leq i \leq Q) 至 输出第 i 个查询的处理结果。
入力例 1
5 2 5 ..#.. ..... ####. ..... #.... 1 1 1 4 1 1 1 1 1 4 4 2 4 2 4 4 4 2 4 3
出力例 1
No Yes No Yes Yes
例如 第 4 个查询将棋子向右移动。 2 通过平行移动一个正方形,您可以在路上没有重叠障碍物的情况下移动。 另一方面 在第 1 次查询中,由于障碍物,棋子无法移动到目的地。
入力例 2
7 3 5 ....... ....... ...#... ....... ....... ..#.... ......# 2 1 1 1 1 1 1 5 3 1 4 4 5 4 1 5 3 1 3 5
出力例 2
Yes No No Yes No