U160226 【2021蓝桥杯中高级组省】T6

2021蓝桥杯中高级组省赛第六题

在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个$ 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表示剩余矩阵方格。 如下图所示：  按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。

输入描述 第一行输入两个以一个空格隔开的正整数 N(2

输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数），如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。

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