分数: 433 分
问题陈述
Takahashi 是一名在大型仓库工作的送货机器人程序员。
仓库楼层分为 N \times N 网格。该单元格位于 r从顶部算起的第行 (1 \leq r \leq N) 和 c左起第 列 (1 \leq c \leq N) 被分配的号码 (r-1) \times N + c。也就是说,单元格编号 1, 2, \ldots, N 从左到右逐行 1,那么 N+1, N+2, \ldots, 2N 从左到右逐行 2,等等。网格上没有墙壁或障碍物,所有单元格都可以通过。
送货机器人正在牢房等待 S。高桥需要将机器人移动到单元的运输区域 T. S 和 T 是不同的单元格。在一次移动中,机器人可以沿四个方向(上、下、左、右)之一将一个单元移动到相邻单元。然而,机器人不能移动到网格之外。
在移动过程中,机器人必须从以下位置收集包裹: M 指定上架。细胞数量 P_1, P_2, \ldots, P_M 给出了装有要收集的包裹的架子所在的位置。 M 单元格可以按任何顺序访问,但所有单元格在到达单元格之前必须至少访问一次 T。请注意,在移动过程中允许多次经过同一单元格。
求机器人从单元格开始所需的最小移动次数 S,访问全部 M 指定单元格,并到达单元格 T。这里,移动次数是指机器人移动到相邻单元格的总次数。
约束
- 1 \leq N \leq 10^5
- 0 \leq M \leq 15
- 1 \leq S \leq N^2
- 1 \leq T \leq N^2
- 1 \leq P_i \leq N^2 (1 \leq i \leq M)
- P_i \neq P_j (i \neq j)
- S, T, P_1, P_2, \ldots, P_M 都是不同的
- 所有输入值均为整数
输入
N M S T P_1 P_2 \cdots P_M
- 第一行包含一个整数 N 表示网格的边长和一个整数 M 代表要访问的单元格数量,以空格分隔。
- 第二行包含一个整数 S 表示起始单元格编号和一个整数 T 代表目标单元格编号,以空格分隔。
- 第三行包含整数 P_1, P_2, \ldots, P_M 代表要访问的单元格编号,以空格分隔。如果 M = 0,未给出第三行。
输出
在一行中打印机器人从单元格启动所需的最小移动次数 S,访问所有指定单元格,并到达单元格 T.
示例输入 1
3 2 1 9 5 3
示例输出 1
6
示例输入 2
5 0 1 25
示例输出 2
8
示例输入 3
100 5 1 10000 505 2550 7523 3001 9999
示例输出 3
270