880033 - 黑白精灵
在一个矩阵精灵王国里有两个精灵,一个叫黑精灵,一个叫白精灵。他们住在一个 N × M 的矩阵方格中的不同位置,黑精灵住在矩阵方格的左上角(1,1),白精灵住在矩阵方格的右下角方格里(N,M)。
在这个矩阵方格例还有一对可穿越的们,这对穿越门的位置不固定,位置可变换(穿越门不会出现在矩阵方格左上角和右下角位置,也不会重叠出现,有且只有一对)。穿越门的功能是当进去其中一扇门的位置后可直接穿越到另一扇门的位置。如下图所示:
一天黑精灵要去白精灵家做客,需要穿过方格矩阵到达白精灵家,穿行矩阵方格要求:
1.每次只能走一个方格,可以向上、向下、向左、向右行走; 2.每走一个方格记为一步,但从一扇门穿越到另一扇门穿越门不记步数(从方格走到穿越门和从穿越门到其他方格都计1步); 3.可借助穿越门去白精灵家(可减少行走步数)。 为了尽快到达白精灵加,请你帮助黑精灵找一条最短路线,并且计算出最短路线的步数。
例如上图中给出一个3*4的矩阵方格,并给出第一个穿越门的坐标位置N1,M1(2,3),第二个穿越门的坐标位置N2,M2(3,1),已知黑精灵初始坐标位置左上角(1,1),白精灵坐标位置右下角(N,M)。按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线,计算出最短路线的步数:
路线:从黑精灵初始位置(1,1)到正下方方格(2,1)走1步,正下方方格(2,1)到其下方穿越门(3,1)走1步,然后穿越到另一扇穿越门(2,3)向正下方(3,3)走1步,最后到大白精灵家(3,4)需要走1步,故最短路线需要4步。
Input
第一行输入两个以一个空格隔开的正整数 N( 2 < N < 101 ), M 2 < M < 101),分别表示 N行 M 列的方格矩阵;
接下来第二行输入两个以一个空格隔开的正整数: N1(N1<=N), M1(M1<=M),代表第一个穿越门位于第 N1行第 M1列;
接下来第三行输入两个以一个空格隔开的正整数: N2( N2<=N), M2(M2<=M),代表第二个穿越门位于第N2行第 M2列;
注意:两个穿越门位置不能重叠,即不能同时满足 N1=N2和M1=M2;两个穿越门位置也不能位于左上角(1,1)和右下角(M,N);第一个穿越门位置要在第二个穿越门前边或者上边。
Output
输出一个整数,表示黑精灵去白精灵家最短路线需要走多少步(可借助穿越门,减少步数)。
Examples
Input
3 4 2 3 3 1
Output
4
Hint
题题目描述较长,但读懂题目以后我们只需要计算曼哈顿距离即可。走穿越门一定不会比不走穿越门更坏,因此分别计算先走穿越门1和先走穿越门2的两种路线的步数,输出较小值即可。