/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は大規模な倉庫で働く配送ロボットのプログラマーです。
倉庫の床は N \times N のグリッド状に区切られています。上から r 行目 (1 \leq r \leq N)、左から c 列目 (1 \leq c \leq N) のマスには番号 (r-1) \times N + c が付けられています。すなわち、1 行目の左から右へ 1, 2, \ldots, N、2 行目の左から右へ N+1, N+2, \ldots, 2N、……というように番号が振られています。グリッド上に壁や障害物はなく、すべてのマスは通行可能です。
配送ロボットは現在、マス S に待機しています。高橋君はロボットをマス T にある出荷エリアまで移動させる必要があります。S と T は異なるマスです。ロボットは 1 回の移動で上下左右に隣接するマスへ 1 マス移動できます。ただし、グリッドの外へ出ることはできません。
ロボットは移動の過程で M 個の指定された棚から荷物を回収しなければなりません。荷物を回収すべき棚のあるマスの番号 P_1, P_2, \ldots, P_M が与えられます。これらの M 個のマスはどのような順序で訪れてもかまいませんが、マス T に到達するまでにすべてのマスを少なくとも 1 回ずつ訪れる必要があります。なお、移動の途中で同じマスを複数回通ることは許されます。
ロボットがマス 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
- 1 行目には、グリッドの一辺の長さを表す整数 N と、経由すべきマスの個数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、開始位置のマス番号を表す整数 S と、終了位置のマス番号を表す整数 T が、スペース区切りで与えられる。
- 3 行目には、経由すべきマスの番号を表す整数 P_1, P_2, \ldots, P_M が、スペース区切りで与えられる。ただし M = 0 のとき、3 行目は与えられない。
出力
ロボットがマス S から出発し、指定されたすべてのマスを訪れてマス T に到達するために必要な最小の移動回数を 1 行で出力してください。
入力例 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
Score : 433 pts
Problem Statement
Takahashi is a programmer for delivery robots working in a large warehouse.
The warehouse floor is divided into an N \times N grid. The cell in the r-th row from the top (1 \leq r \leq N) and the c-th column from the left (1 \leq c \leq N) is assigned the number (r-1) \times N + c. That is, the cells are numbered 1, 2, \ldots, N from left to right in row 1, then N+1, N+2, \ldots, 2N from left to right in row 2, and so on. There are no walls or obstacles on the grid, and all cells are passable.
The delivery robot is currently waiting at cell S. Takahashi needs to move the robot to the shipping area at cell T. S and T are different cells. In one move, the robot can move one cell to an adjacent cell in one of the four directions (up, down, left, right). However, the robot cannot move outside the grid.
During its movement, the robot must collect packages from M designated shelves. The cell numbers P_1, P_2, \ldots, P_M where the shelves with packages to collect are located are given. These M cells may be visited in any order, but all of them must be visited at least once before reaching cell T. Note that passing through the same cell multiple times during movement is allowed.
Find the minimum number of moves required for the robot to start from cell S, visit all M designated cells, and reach cell T. Here, the number of moves refers to the total number of times the robot moves to an adjacent cell.
Constraints
- 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 are all distinct
- All input values are integers
Input
N M S T P_1 P_2 \cdots P_M
- The first line contains an integer N representing the side length of the grid and an integer M representing the number of cells to visit, separated by a space.
- The second line contains an integer S representing the starting cell number and an integer T representing the destination cell number, separated by a space.
- The third line contains integers P_1, P_2, \ldots, P_M representing the cell numbers to visit, separated by spaces. If M = 0, the third line is not given.
Output
Print in one line the minimum number of moves required for the robot to start from cell S, visit all designated cells, and reach cell T.
Sample Input 1
3 2 1 9 5 3
Sample Output 1
6
Sample Input 2
5 0 1 25
Sample Output 2
8
Sample Input 3
100 5 1 10000 505 2550 7523 3001 9999
Sample Output 3
270