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了，可以的话，请您参考添加页面，与大家一起分享你的题解！