Skip to content

1246: 现代迷宫

题目

题目描述

你在某个很大的迷宫里迷路了。这个迷宫可以被看做一个 $n$ 行 $m$ 列的房间阵列。我们用 $(x, y)$ 表示第 $x$ 列第 $y$ 行的房间 $(1 \leq x \leq m, 1 \leq y \leq n)$。

每两个相邻的房间之间都有一扇门。对于每扇门,门关上表示不可通行,门打开表示可以通行。

当门打开时,从门一边的房间走到另一边的房间需要 $1$ 分钟。另外,一些房间中有一个开关,如果连续 $1$ 分钟按住这个开关,那么所有关上的门会打开,所有打开的门会关闭。一共有 $k$ 个开关,他们分别存在于房间 $(x_1, y_1), (x_2, y_2), \cdots (x_k, y_k)$ 中。

现在,形如连接 $(x, y) - (x, y + 1)$ 的房间的门都是打开的,其他的门都是关上的,你现在在房间 $(1, 1)$ ,要在最短时间内移动到房间 $(m, n)$ 。你需要计算并输出这个最短到达时间,如果不可到达,请输出 -1

输入格式

第一行以空格为间隔,输入三个整数 $m, n, k$ 分别表示迷宫的大小和存在开关的房间数量

对于接下来的 $k$ 行的输入,第 $i$ 行输入两个以空格为间隔的整数 $(x_i, y_i)$ ,表示一个存在开关的房间作标

输出格式

输出一行一个整数:表示移动所需的最短时间。如果不能到达房间 $(m, n)$ 则输出 $-1$

样例输入

样例输入 1

text 3 2 1 1 2

样例输入 2

text 3 2 1 2 1

样例输入 3

text 8 9 15 3 1 3 2 3 7 3 8 1 1 4 5 4 3 5 6 5 8 6 3 6 2 7 5 8 9 8 6 8 5

样例输出

样例输出 1

text 4

样例输出 2

text -1

样例输出 3

text 25

数据范围

对于所有数据,$2\leq m, n\leq 10^5, 1\leq k \leq 2\times 10^5, 1\leq x_i\leq m, 1\leq y_i \leq n$.

对于 $40\%$ 的数据,$m, n \leq 1000$

对于额外 $40\%$ 的数据,$k\leq 2000$

时间限制:1000 ms 空间限制:256 mb

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!