(新卷,200分)- 迷宫问题（Java JS Python）

(新卷,200分)- 迷宫问题（Java & JS & Python）

题目描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围： 2≤n,m≤10 ， 输入的内容只包含 0≤val≤1。

输入描述

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述

左上角到右下角的最短路径，格式如样例所示。

用例

题目解析

本题输出描述说

左上角到右下角的最短路径

但是输入描述说

数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

这是不是有点矛盾呢？已经确认只有唯一可达路径了，又何来最短路径一说呢？但是这不影响解题。

本题有两种解题思路：

• 广度优先搜索
• 深度优先搜索

广搜解法更适合本题，关于广度优先搜索的知识

广搜解决本题的难点在于：如何记录路径？

解决方案是，设计一个点类Pos，该类具有三个属性：

• 当前点对象的横坐标x
• 当前点对象的纵坐标y
• 前一个点对象pre

类似于链表节点的定义。这样设计的原因是，广搜过程是一个发射过程，可以简单理解为一个父节点，发散出多个子节点，因此对于每个节点来说都有一个父节点（除了根节点）。

这样当我们找到终点时，就可以沿着pre属性，一直找到起点。

另外，找到终点后，该如何打印路径呢？如果从终点沿着pre属性链打印，那么打印出来的顺序，其实和题目要求的打印顺序是相反的。这里可以采用递归方式打印，即如果一个点存在pre，那么就递归打印其pre点，等pre点打印完了，再回溯打印自身。

广度优先搜索

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let n, m, matrix; rl.on("line", (line) => { lines.push(line); if (lines.length === 1) { [n, m] = lines[0].split(" ").map(Number); } if (n && lines.length === n + 1) { lines.shift(); matrix = lines.map((line) => line.split(" ").map(Number)); getResult(); lines.length = 0; } }); function getResult() { // 广搜队列 const queue = []; // 将（0，0）位置标记为“走过状态”，即将元素值设为2 matrix[0][0] = 2; // 将走过的点加入队列 queue.push(new Pos(0, 0, null)); // 上下左右偏移 const offsets = [ [-1, 0], [1, 0], [0, -1], [0, 1], ]; // 广搜 while (queue.length > 0) { // 当前点 const cur = queue.shift(); // 遍历当前点的上、下、左、右方向的新点 for (let [offsetX, offsetY] of offsets) { // 新点的坐标 const newX = cur.x + offsetX; const newY = cur.y + offsetY; // 如果新点不越界，且未被访问过，且不是墙， 则新点可以访问 if ( newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 0 ) { // 将新点状态设为走过 matrix[newX][newY] = 2; // 将新点和上一个点关联，形成路径链 const next = new Pos(newX, newY, cur); queue.push(next); // 如果新点就是终点，那么则说明找到了起点到终点的路径 if (newX == n - 1 && newY == m - 1) { // 打印路径 printPath(next); // 结束查找 return; } } } } } class Pos { constructor(x, y, pre) { this.x = x; // 当前点的横坐标 this.y = y; // 当前点的纵坐标 this.pre = pre; // 当前点的上一个点（此属性用于形成路径链） } } function printPath(cur) { // 这里采用递归打印，保证打印顺序是起点到终点 if (cur.pre != null) { // 递归的作用是优先打印pre点，pre点打印完，回溯打印cur点 printPath(cur.pre); } console.log(`(${cur.x},${cur.y})`); }

Java算法源码

import java.util.LinkedList; import java.util.Scanner; public class Main { static int n; // 矩阵行数 static int m; // 矩阵列数 static int[][] matrix; // 矩阵 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); matrix = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { matrix[i][j] = sc.nextInt(); } } getResult(); } // 点类 static class Pos { int x; // 当前点的横坐标 int y; // 当前点的纵坐标 Pos pre; // 当前点的上一个点（此属性用于形成路径链） public Pos(int x, int y, Pos pre) { this.x = x; this.y = y; this.pre = pre; } } public static void getResult() { // 广搜队列 LinkedList<Pos> queue = new LinkedList<>(); // 将（0，0）位置标记为“走过状态”，即将元素值设为2 matrix[0][0] = 2; // 将走过的点加入队列 queue.add(new Pos(0, 0, null)); // 上下左右偏移量 int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 广搜 while (queue.size() > 0) { // 当前点 Pos cur = queue.removeFirst(); // 遍历当前点的上、下、左、右方向的新点 for (int[] offset : offsets) { // 新点的坐标 int newX = cur.x + offset[0]; int newY = cur.y + offset[1]; // 如果新点不越界，且未被访问过，且不是墙， 则新点可以访问 if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 0) { // 将新点状态设为走过 matrix[newX][newY] = 2; // 将新点和上一个点关联，形成路径链 Pos next = new Pos(newX, newY, cur); queue.add(next); // 如果新点就是终点，那么则说明找到了起点到终点的路径 if (newX == n - 1 && newY == m - 1) { // 打印路径 printPath(next); // 结束查找 return; } } } } } public static void printPath(Pos cur) { // 这里采用递归打印，保证打印顺序是起点到终点 if (cur.pre != null) { // 递归的作用是优先打印pre点，pre点打印完，回溯打印cur点 printPath(cur.pre); } System.out.println("(" + cur.x + "," + cur.y + ")"); } }

Python算法源码

# 输入获取 n, m = map(int, input().split()) matrix = [list(map(int, input().split())) for i in range(n)] class Pos: def __init__(self, x, y, pre): self.x = x # 当前点的横坐标 self.y = y # 当前点的纵坐标 self.pre = pre # 当前点的上一个点（此属性用于形成路径链） def printPath(cur): # 这里采用递归打印，保证打印顺序是起点到终点 if cur.pre: # 递归的作用是优先打印pre点，pre点打印完，回溯打印cur点 printPath(cur.pre) print(f"({cur.x},{cur.y})") # 算法入口 def getResult(): # 广搜队列 queue = [] # 将（0，0）位置标记为“走过状态”，即将元素值设为2 matrix[0][0] = 2 # 将走过的点加入队列 queue.append(Pos(0, 0, None)) # 上下左右偏移量 offsets = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 广搜 while len(queue) > 0: # 当前点 cur = queue.pop(0) # 遍历当前点的上、下、左、右方向的新点 for offsetX, offsetY in offsets: # 新点的坐标 newX = cur.x + offsetX newY = cur.y + offsetY # 如果新点不越界，且未被访问过，且不是墙， 则新点可以访问 if n > newX >= 0 and m > newY >= 0 and matrix[newX][newY] == 0: # 将新点状态设为走过 matrix[newX][newY] = 2 # 将新点和上一个点关联，形成路径链 nxt = Pos(newX, newY, cur) queue.append(nxt) # 如果新点就是终点，那么则说明找到了起点到终点的路径 if newX == n - 1 and newY == m - 1: # 打印路径 printPath(nxt) # 结束查找 return # 算法调用 getResult()

深度优先搜索

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let n, m, matrix; rl.on("line", (line) => { lines.push(line); if (lines.length === 1) { [n, m] = lines[0].split(" ").map(Number); } if (n && lines.length === n + 1) { lines.shift(); matrix = lines.map((line) => line.split(" ").map(Number)); getResult(); lines.length = 0; } }); function getResult() { // 记录符合可以从(0,0)走到(n-1,m-1)的路径 const ans = []; // 将(0,0)位置标记为走过，值为2假设为走过，避免重复走 matrix[0][0] = 2; dfs(0, 0, [], ans); // 由于输入描述说：数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 // 因此ans只有一个解 for (let [x, y] of ans) { console.log(`(${x},${y})`); } } // 上下左右偏移 const offsets = [ [-1, 0], [1, 0], [0, -1], [0, 1], ]; function dfs(x, y, path, ans) { // 如果当前点(x,y)就是终点(n-1, m-1)，则找到路径 if (x == n - 1 && y == m - 1) { path.push([x, y]); // 将路径加入结果集ans中 ans.push(...path); return true; } // 否则，向当前点上下左右四个方向继续深搜 for (let [offsetX, offsetY] of offsets) { const newX = x + offsetX; const newY = y + offsetY; // 如果新点不越界，且未走过 if ( newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 0 ) { // 则加入路径 path.push([x, y]); // 同时将新点标记为走过 matrix[newX][newY] = 2; // 基于新点，继续深搜 const res = dfs(newX, newY, path, ans); // 如果该分支可以到达终点，则结束深搜 if (res) return true; // 回溯 matrix[newX][newY] = 0; path.pop(); } } }

Java算法源码

import java.util.LinkedList; import java.util.Scanner; public class Main { static int n; // 矩阵行数 static int m; // 矩阵列数 static int[][] matrix; // 矩阵 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); matrix = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { matrix[i][j] = sc.nextInt(); } } getResult(); } // 记录符合可以从(0,0)走到(n-1,m-1)的路径 static LinkedList<String> ans = new LinkedList<>(); public static void getResult() { // 将(0,0)位置标记为走过，值为2假设为走过，避免重复走 matrix[0][0] = 2; // 从(0,0)点开始深搜 dfs(0, 0, new LinkedList<>()); // 由于输入描述说：数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 // 因此ans只有一个解 for (String an : ans) { System.out.println(an); } } // 上下左右偏移量 static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public static boolean dfs(int x, int y, LinkedList<String> path) { // 如果当前点(x,y)就是终点(n-1, m-1)，则找到路径 if (x == n - 1 && y == m - 1) { path.add("(" + x + "," + y + ")"); // 将路径加入结果集ans中 ans.addAll(path); return true; } // 否则，向当前点上下左右四个方向继续深搜 for (int[] offset : offsets) { // 新点位置(newX, newY) int newX = x + offset[0]; int newY = y + offset[1]; // 如果新点不越界，且未走过 if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 0) { // 则加入路径 path.add("(" + x + "," + y + ")"); // 同时将新点标记为走过 matrix[newX][newY] = 2; // 基于新点，继续深搜 boolean res = dfs(newX, newY, path); // 如果该分支可以到达终点，则结束深搜 if (res) return true; matrix[newX][newY] = 0; path.removeLast(); } } return false; } }

Python算法源码

# 输入获取 n, m = map(int, input().split()) matrix = [list(map(int, input().split())) for i in range(n)] # 上下左右偏移量 offsets = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 记录符合可以从(0,0)走到(n-1,m-1)的路径 ans = [] # 深搜 def dfs(x, y, path): global ans # 如果当前点(x,y)就是终点(n-1, m-1)，则找到路径 if x == n - 1 and y == m - 1: path.append((x, y)) # 将路径加入结果集ans中 ans = path[:] return True # 否则，向当前点上下左右四个方向继续深搜 for offsetX, offsetY in offsets: # 新点位置(newX, newY) newX = x + offsetX newY = y + offsetY # 如果新点不越界，且未走过 if 0 <= newX < n and 0 <= newY < m and matrix[newX][newY] == 0: # 则加入路径 path.append((x, y)) # 同时将新点标记为走过 matrix[newX][newY] = 2 # 基于新点，继续深搜 res = dfs(newX, newY, path) # 如果该分支可以到达终点，则结束深搜 if res: return True # 回溯 matrix[newX][newY] = 0 path.pop() # 算法入口 def getResult(): # 将(0,0)位置标记为走过，值为2假设为走过，避免重复走 matrix[0][0] = 2 # 从(0,0)点开始深搜 dfs(0, 0, []) # 由于输入描述说：数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 # 因此ans只有一个解 for an in ans: print(an) # 算法调用 getResult()