{"problem":{"name":"[yLOI2023] 云梦谣","description":{"content":"“喂，枸杞，你这只笨狗，又偷吃！看我不收拾你！” 朵一气呼呼地从院子里跑出来，手中握着掸子，而枸杞早已不见踪影。 云梦庭可以看作一个 $n$ 行 $m$ 列的方格阵，第 $i$ 行第 $j$ 列的格子被记作 $(i,j)$。每个格子 $(i,j)$ 要么有一个高度 $h_{i,j}$（$h_{i,j}$ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的 $h_{i,j}$ 用 $0","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9065"},"statements":[{"statement_type":"Markdown","content":"“喂，枸杞，你这只笨狗，又偷吃！看我不收拾你！”\n\n朵一气呼呼地从院子里跑出来，手中握着掸子，而枸杞早已不见踪影。\n\n云梦庭可以看作一个 $n$ 行 $m$ 列的方格阵，第 $i$ 行第 $j$ 列的格子被记作 $(i,j)$。每个格子 $(i,j)$ 要么有一个高度 $h_{i,j}$（$h_{i,j}$ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的 $h_{i,j}$ 用 $0$ 表示。）另外，云梦庭上有 $k$ 个指定的格子上可以进行**御剑飞行**。开始时，朵一和枸杞分别位于方格 $(1,1)$ 和 $(n,m)$。\n\n朵一的御剑飞行还不是很熟练，现在她还控制不好御剑的高度。因此在任意时刻，朵一在方格 $(i,j)$ 上可以做如下行动之一：\n\n- 移动到与该方格相邻的方格 $(i-1,j)$、$(i+1,j)$、$(i,j-1)$、$(i,j+1)$ 之一上（不能移动出方格边界，也不能移动到障碍物上）；\n- 如果方格 $(i,j)$ 上允许御剑飞行，则朵一可以御剑飞行至另一个**同样允许御剑飞行且与方格 $(i,j)$ 高度相等的方格上**；\n- 使用仙法将当前格子的高度 $h_{i,j}$ 改变为任一正整数。\n\n进行上述每项行动均需花费 $1$ 个单位时间。\n\n“哼，笨狗子你再跑！”说罢，朵一便追了出去。朵一接下来还要尽快继续今天的修行，因此她想知道到达 $(n,m)$ 格子所需的最短时间是多少。\n\n## Input\n\n输入的第一行有三个整数，依次表示方格阵的行数 $n$、列数 $m$ 和能御剑飞行的方格个数 $k$。  \n接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数表示方格 $(i,j)$ 的高度 $h_{i,j}$。数据保证 $h_{1,1}$ 和 $h_{n,m}$ 不为 $0$。  \n接下来 $k$ 行，每行两个整数 $x$ 和 $y$，表示一个允许御剑飞行的方格的坐标 $(x, y)$。数据保证这 $k$ 个方格的坐标互不相同。\n\n## Output\n\n一行一个整数，表示朵一到达 $(n,m)$ 所需的最小时间。如果朵一无法到达，输出 ```-1```。\n\n[samples]\n\n## Background\n\n> 归来且做云梦梦一场 大梦好  \n> 栽花闻酒香 醒醒醉醉笑笑  \n> 天地偌大复路远山高 最难得偷半日逍遥  \n> 偶尔糊涂不问世事不知晓\n\n——银临 & 慕寒《云梦谣》\n\n## Note\n\n### 样例 1 解释\n\n第 $1$ 个单位时间，朵一将当前方格 $(1,1)$ 的高度修改为 $4$；  \n第 $2$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(3,4)$；  \n第 $3$ 个单位时间，朵一从方格 $(3,4)$ 移动到 $(4,4)$，追上了枸杞。\n\n### 样例 2 解释\n\n第 $1$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(4,1)$；  \n第 $2$ 个单位时间，朵一从方格 $(4,1)$ 移动到 $(4,2)$；  \n第 $3$ 个单位时间，朵一从方格 $(4,2)$ 移动到 $(4,3)$；  \n第 $4$ 个单位时间，朵一从方格 $(4,3)$ 移动到 $(4,4)$，追上了枸杞。\n\n### 数据规模与约定\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/f2epmv84.png)\n\n对全部的测试点，保证 $1 \\leq n, m \\leq 3 \\times 10^3$，$0 \\leq k,h_{i,j} \\leq n \\times m$。\n### 提示\n\n请注意大量数据读入对程序效率造成的影响，选择合适的读入方式，避免超时。\n\n### 说明\n\n本题共有 5 个附加样例文件，见附件里的 dream.zip。\n\n### 后记\n\n不过，别看朵一现在一副生气的样子，可当她追上枸杞后，大抵是不舍得真的动手吧。“嘿嘿，今日的修行结束后，该吃什么好呢？”在这飞瀑悬挂、翠竹怀抱的云梦庭中，修仙炼体，不羡尘嚣，应是这世上最逍遥的事了。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9065","tags":["2023","O2优化","洛谷月赛"],"sample_group":[["4 4 2\n1 2 3 4\n1 2 3 4\n1 2 3 4\n1 2 3 4\n1 1\n3 4","3"],["4 4 3\n1 2 3 4\n1 2 3 4\n1 2 3 4\n1 2 3 4\n1 1\n2 4\n4 1","4"],["2 5 0\n1 0 3 3 4\n2 3 4 0 5","7"],["4 4 3\n1 1 1 0\n1 1 0 1\n1 0 1 1\n0 1 1 1\n1 1\n2 1\n3 3","3"]],"created_at":"2026-03-03 11:09:25"}}