AT_bcu30_e スライドパズル

你正在玩一个滑块拼图游戏。这个游戏利用一个 $N \times N$ 的正方形棋盘，其中某些格子上可能放置了障碍物，但也有可能完全没有障碍物。棋盘上有一个可以滑动的棋子，它的大小是 $K \times K$。 这个棋子可以在棋盘上不碰到障碍物的地方滑动，且允许向上下左右四个方向进行平行移动，但不能超出棋盘的边界或与障碍物重叠。 你的任务是处理 $Q$ 个查询。对于每个查询，判断从初始位置 $(r_1, c_1)$ 开始，如果能通过滑动将棋子的左上角移到目标位置 $(r_2, c_2)$，则输出 `Yes`，否则输出 `No`。

输入的第一行为三个整数，分别表示 $N$、$K$ 和 $Q$。接下来 $N$ 行，每行包含 $N$ 个字符 `.` 或 `#`，描述棋盘布置：`#` 表示该格子有障碍物，`.` 表示没有障碍物。 然后是 $Q$ 个查询，每个查询由四个整数 $r_1$、$c_1$、$r_2$、$c_2$ 描述，表示起始和目标位置。对于每个查询，起始和目标位置的 $K \times K$ 区域内都没有障碍物。

对于每个查询输出一行，若能通过滑动到达目标位置输出 `Yes`，否则输出 `No`。

- $1 \leq N \leq 1000$ - $1 \leq K \leq N$ - $1 \leq Q \leq 100000$ - $s_{ij}$ 是 `.` 或 `#` - 起始和目标的 $K \times K$ 区域均无障碍物 在每次查询中，起始和目标位置保证是有效的，即不会有障碍物干扰。 **本翻译由 AI 自动生成**