P7863 「EVOI-RD1」飞鸟和蝉

你骄傲地飞远，我栖息的叶片。 听不见的宣言，重复过很多年。 沧海月的想念羽化我昨天， 在我成熟的笑脸， 你却未看过一眼。

蝉 Charlie 要去寻找他的好朋友飞鸟了。 具体来说，Charlie 和他的好朋友生活的地方可以看作一个 $n \times m$ 的网格，左上角为 $(1,1)$，右下角为 $(n,m)$。每个格子 $(i,j)$ 有一个海拔高度 $h_{i,j}$。Charlie 的目标是从他的家 $(x_0,y_0)$ 出发，不重不漏地经过网格中的每个格子**恰好一次**，**最终回到自己的家** $(x_0,y_0)$。Charlie 有两种移动方式： 1. 跳跃。用这种方式，Charlie 可以到达上下左右 $4$ 个相邻格子中**海拔严格低于当前格子**的一个格子。注意跳跃不消耗体力。 2. 飞行。用这种方式，Charlie 可以从当前格子 $(x,y)$ 到达网格中**任意一个**格子 $(x',y')$，并消耗 $h_{x',y'}-h_{x,y}$ 个单位的体力。**注意飞行所消耗的体力值可以是负数**。 Charlie 希望用尽量少的飞行次数完成目标，**在此前提下**再令消耗的体力最少。由于网格实在太大了，Charlie 希望你能帮助他。

无

无

**本题采用捆绑测试** 样例 1 解释：从 $(1,1)$ 飞到 $(2,2)$，再绕一圈即可。 样例 2 解释：一种最佳方案为：$(2,3)-(1,3)-(1,2)-(1,1)=(2,1)-(3,1)=(2,2)=(3,2)=(3,3)=(2,3)$，其中 $=$ 代表飞行。 - Subtask 1 (10 pts)：满足 $1 \leq n,m \leq 3$。 - Subtask 2 (20 pts)：满足 $1 \leq n,m \leq 5$。 - Subtask 3 (20 pts)：保证至多有两种不同的海拔高度。 - Subtask 4 (50 pts)：无特殊限制。 对于 $100\%$ 的数据： - $1 \leq n,m \leq 50$。 - $1 \leq x_0 \leq n,1 \leq y_0 \leq m,1 \leq h_{i,j} \leq 10^9$。 出题人：[冷月葬T魂](https://www.luogu.com.cn/user/340903)