原神迷宫：D++的逃脱之路 - 使用BFS算法求解最短路径

{"title":"经过你的帮助，D++在114514年终于打开了原神，但他遇到了一个大麻烦——长丙文。\nD++想要摆脱长丙文的追捕，就必须逃出这张图，图中的格子都有技能，技能列表如下所示：\n\n1. . :表示空地，可以直接走过去。\n\n2. # :表示墙，无法走过去。\n\n3. ? :表示传送门，可以直接到达终点。\n\n\n第一行六个整数：n ，m ，a1 ，a2 ，b1 ，b2 表示地图的行与列，起点与终点。\n\n接下来有 n 行 m 列的字符图。表示地图。\n\n\n共一行，一个整数，表示从 a 点到 b 点所需要的最少步数，若无法到达终点，则输出 -1 。\n\n样例 #1 \n\n样例输入 #1\n\n2 2 1 1 2 2\n..\n..\n\n样例输出 #1\n\n2\n\n样例 #2\n\n样例输入 #2\n\n3 3 1 1 3 3\n...\n?##\n...\n\n样例输出 #2\n\n2\n\n\nn<20,m<20\n\n根据上述题意，出十组高级数据内容：高级数据1：\n\n输入：\n5 5 1 1 5 5\n.....\n.#.#.\n.#?#.\n.#.#.\n.....\n\n输出：\n8\n\n解释：\n起点到终点的最短路径为：(1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3) -> (4,3) -> (5,3) -> (5,4) -> (5,5)，共8步。\n\n高级数据2：\n\n输入：\n4 4 1 1 4 4\n....\n?..#\n.#.#\n..#.\n\n输出：\n-1\n\n解释：\n起点无法到达终点。\n\n高级数据3：\n\n输入：\n5 5 1 1 5 5\n.....\n.#..#\n..#?#\n.#.#.\n.....\n\n输出：\n12\n\n解释：\n起点到终点的最短路径为：(1,1) -> (1,2) -> (2,2) -> (3,2) -> (4,2) -> (5,2) -> (5,3) -> (4,3) -> (3,3) -> (3,4) -> (4,4) -> (5,4) -> (5,5)，共12步。\n\n高级数据4：\n\n输入：\n6 6 1 1 6 6\n......\n.#.#..\n.#.?..\n..##..\n.###..\n......\n\n输出：\n-1\n\n解释：\n起点无法到达终点。\n\n高级数据5：\n\n输入：\n5 5 1 1 5 5\n.....\n.#.#.\n.#?#.\n.#.#.\n.....\n\n输出：\n8\n\n解释：\n起点到终点的最短路径为：(1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3) -> (4,3) -> (5,3) -> (5,4) -> (5,5)，共8步。\n\n高级数据6：\n\n输入：\n4 4 1 1 4 4\n....\n?..#\n.#.#\n..#.\n\n输出：\n-1\n\n解释：\n起点无法到达终点。\n\n高级数据7：\n\n输入：\n5 5 1 1 5 5\n.....\n.#..#\n..#?#\n.#.#.\n.....\n\n输出：\n12\n\n解释：\n起点到终点的最短路径为：(1,1) -> (1,2) -> (2,2) -> (3,2) -> (4,2) -> (5,2) -> (5,3) -> (4,3) -> (3,3) -> (3,4) -> (4,4) -> (5,4) -> (5,5)，共12步。\n\n高级数据8：\n\n输入：\n6 6 1 1 6 6\n......\n.#.#..\n.#.?..\n..##..\n.###..\n......\n\n输出：\n-1\n\n解释：\n起点无法到达终点。\n\n高级数据9：\n\n输入：\n5 5 1 1 5 5\n.....\n.#.#.\n.#?#.\n.#.#.\n.....\n\n输出：\n8\n\n解释：\n起点到终点的最短路径为：(1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3) -> (4,3) -> (5,3) -> (5,4) -> (5,5)，共8步。\n\n高级数据10：\n\n输入：\n4 4 1 1 4 4\n....\n?..#\n.#.#\n..#.\n\n输出：\n-1\n\n解释：\n起点无法到达终点。