1229: 最短距离
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:43
Solved:25
Description
在一个矩阵精灵王国里有两个精灵,一个叫黑精灵,一个叫白精灵。
他们住在一个 $n\times m$ 的矩阵方格中的不同位置。黑精灵住在左上角方格($1,1$),白精灵住在右下角方格($n,m$)。
在这个矩阵方格里还有一对可穿越的门,这对穿越门的位置不固定,位置可变换。(穿越门不会出现在矩阵的左上角和右下角位置,也不会重叠出现,有且只有一对)。穿越门的功能是当进入其中一扇门的位置后可直接穿越到另一扇门的位置。
下图为一个 $3\times 4$ 的矩阵:
有一天黑精灵要去白精灵家做客,需要穿过方格矩阵到达白精灵的家,穿行方格矩阵过程要求如下:
- 每次只能走一个方格,可以向上下左右四个方向移动;
- 每走一个方格计为 $1$ 步,但从一个穿越门穿越到另一个穿越门不计步数;
请你帮助黑精灵设计一条最佳路线,使得其能花费最少步数到白精灵家。
他们住在一个 $n\times m$ 的矩阵方格中的不同位置。黑精灵住在左上角方格($1,1$),白精灵住在右下角方格($n,m$)。
在这个矩阵方格里还有一对可穿越的门,这对穿越门的位置不固定,位置可变换。(穿越门不会出现在矩阵的左上角和右下角位置,也不会重叠出现,有且只有一对)。穿越门的功能是当进入其中一扇门的位置后可直接穿越到另一扇门的位置。
下图为一个 $3\times 4$ 的矩阵:
有一天黑精灵要去白精灵家做客,需要穿过方格矩阵到达白精灵的家,穿行方格矩阵过程要求如下:
- 每次只能走一个方格,可以向上下左右四个方向移动;
- 每走一个方格计为 $1$ 步,但从一个穿越门穿越到另一个穿越门不计步数;
请你帮助黑精灵设计一条最佳路线,使得其能花费最少步数到白精灵家。
Input
共三行。
第一行,包含两个正整数 $n$ 和 $m$,中间以空格隔开,分别表示矩阵方格的行数和列数。
第二行,包含两个正整数 $x_1$ 和 $y_1$,中间以空格隔开,表示第一个穿越门在第 $x_1$ 行第 $y_1$ 列。
第三行,包含两个正整数 $x_2$ 和 $y_2$,中间以空格隔开,表示第二个穿越门在第 $x_2$ 行第 $y_2$ 列。
第一行,包含两个正整数 $n$ 和 $m$,中间以空格隔开,分别表示矩阵方格的行数和列数。
第二行,包含两个正整数 $x_1$ 和 $y_1$,中间以空格隔开,表示第一个穿越门在第 $x_1$ 行第 $y_1$ 列。
第三行,包含两个正整数 $x_2$ 和 $y_2$,中间以空格隔开,表示第二个穿越门在第 $x_2$ 行第 $y_2$ 列。
Output
输出黑精灵到白精灵家需要的最少步数。
Sample Input Copy
3 4
2 3
3 1
Sample Output Copy
4
HINT
数据范围:
$3\le n,m \le 100$,$1\le x_1,x_2 \le n$,$1\le y_1,y_2 \le m$。
$3\le n,m \le 100$,$1\le x_1,x_2 \le n$,$1\le y_1,y_2 \le m$。