(C卷,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表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述

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

用例

输入	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
输出	(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
说明	无

输入	5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0
输出	(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)
说明	注意：不能斜着走！！

题目解析

本题输出描述说

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

但是输入描述说

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

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

本题有两种解题思路：

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

广搜解法更适合本题，关于广度优先搜索的知识，可以看下：

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

解决方案是，设计一个点类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()

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=c%e5%8d%b7200%e5%88%86-%e8%bf%b7%e5%ae%ab%e9%97%ae%e9%a2%98%ef%bc%88java-js-python%ef%bc%89，转载请注明出处。

2024华为OD机试题库