3954: 蓝桥杯C++省赛（12）：最短距离

最短距离

题目描述：

在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中

的不同位置，黑精灵住在矩阵方格的左上角方格里(1,1)，白精灵住在矩阵方格的右下角方格里(N,M)。

在这个矩阵方格里还有一对可穿越的门，这对穿越门的位置不固定，位置可变换（穿越门不会出现在矩

阵方格左上角和右下角位置，也不会重叠出现，有且只有一对)。穿越门的功能是当进入其中一扇门的

位置后可直接穿越到另一扇门的位置。

如下图所示：

一天黑精灵要去白精灵家做客，需要穿过方格矩阵到达白精灵家，穿行矩阵方格要求：

1.每次只能走一个方格，可以向上、向下、向左、向右行走；

2.每走一个方格计为1步，但从一扇穿越门穿越到另一扇穿越门不记步数（从方格走到穿越门和从穿

越门到其他方格都计1步)；

3.可借助穿越门去白精灵家（可减少行走步数)。

为了尽快到达白精灵家，请你帮助黑精灵找一条最短路线，并且计算出最短路线的步数。

例如：

给出一个3*4矩阵方格，并给出第一个穿越门的坐标位置N1,M1(2,3),，第二个穿越门的坐标位

置N2,M2(3,1),已知黑精灵初始坐标位置左上角(1,1)，白精灵坐标位置右下角(N,

M)

假设用两个大写字母“D”表示矩阵方格中穿越门位置，1代表黑精灵，2代表白精灵，用数字0表示

剩余矩阵方格。

如下图所示：

按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线

的步数。

路线：从黑精灵初始位置(1,1)到正下方方格(2,1)走1步，正下方方格(2,1)到其下方穿越门(3,1)“D”走1步，然后穿越到另一扇穿越门(2,3)向正下方(3,3)走1步，最后到达白精灵家（3,4)需要走1步，故最短路线需要4步。

输入描述：

第一行输入两个以一个空格隔开的正整数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)；第一个穿越门位置要在第二个穿越门前边或者上边。

输出描述：

输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数）。

输入样例：

3 4

2 3

3 1

输出样例：

4

第一行输入两个以一个空格隔开的正整数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)；第一个穿越门位置要在第二个穿越门前边或者上边。

3 4
2 3
3 1

4