[常州市赛 2021] 移动

Luogu

IDLGB4208

Time1000ms

Memory128MB

DifficultyP4

搜索图论2021江苏广度优先搜索 BFS最短路科创活动小学活动

小 $\text X$ 学校的教学楼是一栋 $H$ 层的建筑。学生在同一楼层间可以自由移动，但是只有通过爬楼梯才可以上下楼层。让我们把教学楼抽象成一个有 $H\times M$ 个格子的矩形，学生可以从一个单元格上花费 $1$ 秒移动到上下左右的相邻单元格上。学生在水平方向上的移动是没有限制的（除了不能摔出楼外），但只有在有楼梯相连的时候才能进行竖直移动。一个楼梯会连接同一列中的一段连续楼层，**且一列中只会有一个楼梯**。**对于这一部分叙述可以通过样例理解**。现在有 $T$ 个学生，每个人都希望从一个位置走到另一个位置上。他们想问问小 $\text X$ 最短需要花费多长时间。 ## Input 第一行，$2$ 个整数 $H$ 和 $M$ 表示教学楼大小。第二行，$1$ 个整数 $K$ 表示楼梯的数量。接下来 $K$ 行，每行三个整数 $x,h_1,h_2$ 表示在第 $x$ 列的 $h_1$ 层和 $h_2$ 层之间有楼梯。接下来 $1$ 行，一个整数 $T$ 表示有 $T$ 个学生。接下来 $T$ 行，每行四个整数 $s_x,s_y,t_x,t_y$ 表示这个学生想要从 $s_x$ 列的 $s_y$ 层走到 $t_x$ 列的 $ty$ 层。 ## Output 对于每一个学生按顺序输出一行一个整数表示最短时间。如果不可能走到，输出 `-1`。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/444>。数据为民间数据。 ## Note ### 样例解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/tdx69my8.png) ### 数据范围对于所有数据，$1\le x\le M$ 且所有 $x$ 各不相同，$1\le h_1<h_2\le H,1\le s_x,t_x\le M,1\le s_y,t_y\le H,1\le H,M\le 10^5,1\le K\le 300,1\le T\le 5 \times 10^4$。

Samples

Input #1

Output #1

6
9
-1

API Response (JSON)

{
  "problem": {
    "name": "[常州市赛 2021] 移动",
    "description": {
      "content": "小 $\\text X$ 学校的教学楼是一栋 $H$ 层的建筑。学生在同一楼层间可以自由移动，但是只有通过爬楼梯才可以上下楼层。   让我们把教学楼抽象成一个有 $H\\times M$ 个格子的矩形，学生可以从一个单元格上花费 $1$ 秒移动到上下左右的相邻单元格上。学生在水平方向上的移动是没有限制的（除了不能摔出楼外），但只有在有楼梯相连的时候才能进行竖直移动。一个楼梯会连接同一列中的一段连续楼层",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4208"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 $\\text X$ 学校的教学楼是一栋 $H$ 层的建筑。学生在同一楼层间可以自由移动，但是只有通过爬楼梯才可以上下楼层。  \n让我们把教学楼抽象成一个有 $H\\times M$ 个格子的矩形，学生可以从一个单元格上花费 $1$ 秒移动到上下左右的相邻单元格上。学生在水平方向上的移动是没有限制的（除了不能摔出楼外），但只有在有楼梯相连的时候才能进行竖直移动。一个楼梯会连接同一列中的一段连续楼层...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments