题目详情题解（0）讨论（0）提交记录（0）

AT_bcu30_e.スライドパズル

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你正在玩一个滑块拼图游戏。这个游戏利用一个 N×NN \times N 的正方形棋盘，其中某些格子上可能放置了障碍物，但也有可能完全没有障碍物。棋盘上有一个可以滑动的棋子，它的大小是 K×KK \times K。

这个棋子可以在棋盘上不碰到障碍物的地方滑动，且允许向上下左右四个方向进行平行移动，但不能超出棋盘的边界或与障碍物重叠。

你的任务是处理 QQ 个查询。对于每个查询，判断从初始位置 (r1,c1)(r_1, c_1) 开始，如果能通过滑动将棋子的左上角移到目标位置 (r2,c2)(r_2, c_2)，则输出 Yes，否则输出 No。

输入格式

输入的第一行为三个整数，分别表示 NN、KK 和 QQ。接下来 NN 行，每行包含 NN 个字符 . 或 #，描述棋盘布置：# 表示该格子有障碍物，. 表示没有障碍物。

然后是 QQ 个查询，每个查询由四个整数 r1r_1、c1c_1、r2r_2、c2c_2 描述，表示起始和目标位置。对于每个查询，起始和目标位置的 K×KK \times K 区域内都没有障碍物。

输出格式

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

输入输出样例

  • 输入#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

  • 输入#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

说明/提示

  • 1≤N≤10001 \leq N \leq 1000
  • 1≤K≤N1 \leq K \leq N
  • 1≤Q≤1000001 \leq Q \leq 100000
  • sijs_{ij} 是 . 或 #
  • 起始和目标的 K×KK \times K 区域均无障碍物

在每次查询中，起始和目标位置保证是有效的，即不会有障碍物干扰。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页