第十一题黑精灵与白精灵 【题目描述】 在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中的不同位置，黑精灵住在矩阵方格的左上角(1，1)，白精灵住在矩阵方格

第十一题.黑精灵与白精灵pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【题目描述】pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中的不同位置，黑精灵住在矩阵方格的左上角(1，1)，白精灵住在矩阵方格的右下角方格里(N，M)。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

在这个矩阵方格例还有一对可穿越的们，这对穿越门的位置不固定，位置可变换(穿越门不会出现在矩阵方格左上角和右下角位置，也不会重叠出现，有且只有一对)。穿越门的功能是当进去其中一扇门的位置后可直接穿越到另一扇门的位置。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如下图所示：pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

一天黑精灵要去白精灵家做客，需要穿过方格矩阵到达白精灵家，穿行矩阵方格要求：pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1.每次只能走一个方格，可以向上、向下、向左、向右行走;pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2.每走一个方格记为一步，但从一扇门穿越到另一扇门穿越门不记步数(从方格走到穿越门和从穿越门到其他方格都计1步);pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3.可借助穿越门去白精灵家(可减少行走步数)。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

为了尽快到达白精灵加，请你帮助黑精灵找一条最短路线，并且计算出最短路线的步数。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

例如：pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

给出一个3*4的矩阵方格，并给出第一个穿越门的坐标位置N1，M1(2，3)，第二个穿越门的坐标位置N2，M2(3，1)，已知黑精灵初始坐标位置左上角(1，1)，白精灵坐标位置右下角(N，M)。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

假设用两个大写字母“D”表示矩阵方格中穿越门的位置，1代表黑精灵，2代表白精灵，用数字0表示剩余矩阵方格。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如下图所示：pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

路线：从黑精灵初始位置(1，1)到正下方方格(2，1)走1步，正下方方格(2，1)到其下方穿越们(3，1)“D”走1步，然后穿越到另一扇穿越门(2，3)向正下方(3，3)走1步，最后到大白精灵家(3，4)需要走1步，故最短路线需要4步。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输入描述】pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一行输入两个以一个空格隔开的正整数N(2pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来第二行输入两个以一个空格隔开的正整数：N1(N1<=N)，M1(M1<=M)，代表第一个穿越门位于第N1行第M1列;pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来第三行输入两个以一个空格隔开的正整数：N2(N2<=N)，M2(M2<=M)，代表第二个穿越门位于第N2行第M2列;pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

注意：两个穿越门位置不能重叠，即不能同时满足N1=N2和M1=M2;两个穿越门位置也不能位于左上角(1，1)和右下角(M，N);第一个穿越门位置要在第二个穿越门前边或者上边。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输出描述】pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步(可借助穿越门，减少步数)，如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输入样例】pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3 4pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2 3pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3 1pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输出样例】pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4pjZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库