华为OD机试：迷宫问题

题目描述

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

输出描述

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

用例

题目解析

1.首先，我们需要定义一个二维数组maze，用于存储迷宫的信息。

2.然后，我们需要定义一个函数find_path，用于寻找从左上角到右下角的最短路径。

3.在find_path函数中，我们需要使用深度优先搜索（DFS）算法来遍历迷宫，找到一条从左上角到右下角的路径。

4.在DFS算法中，我们需要记录当前位置的坐标（x, y），以及已经走过的路径。

5.当到达右下角时，说明找到了一条路径，将其输出并返回。

6.如果当前位置是墙壁或者已经走过，则跳过该位置。

7.如果当前位置可以走，则继续向上下左右四个方向进行DFS搜索。

8.最后，调用find_path函数，输出结果。

JS算法源码

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 = [];

  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) {
 
    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 {
        private int x;
        private int y;
        private 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<>();

        matrix[0][0] = 2;
        queue.addFirst(new Pos(0, 0, null));

        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            Pos cur = queue.removeLast();

            for (int[] offset : offsets) {
                int newX = cur.x + offset[0];
                int newY = cur.y + offset[1];

                if (isValid(newX, newY)) {
                    matrix[newX][newY] = 2;
                    Pos next = new Pos(newX, newY, cur);
                    queue.addFirst(next);

                    if (newX == n - 1 && newY == m - 1) {
                        printPath(next);
                        return;
                    }
                }
            }
        }
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] == 0;
    }

    public static void printPath(Pos cur) {
        if (cur != null) {
            printPath(cur.pre);
            System.out.println("(" + cur.x + "," + cur.y + ")");
        }
    }
}

Python算法源码

from collections import deque

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:
        printPath(cur.pre)
    print(f"({cur.x},{cur.y})")

def getResult():
    queue = deque()
    matrix[0][0] = 2
    queue.append(Pos(0, 0, None))

    offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

    while queue:
        cur = queue.popleft()

        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()