← 返回题目列表

AtCoder · bcu30_e

E. 幻灯片拼图

中文机器翻译题面 查看原题

配点 : 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