首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题

热度指数：224673 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 有一个 $h$ 行 $w$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格要么是可以通过的空方格 $\texttt{`0'}$ ，要么是不可通过的墙方格 $\texttt{`1'}$ ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 $(x,y)$ 向上移动一格即抵达 $(x-1,y)$ 、向下移动一格即抵达 $(x+1,y)$ 、向左移动一格即抵达 $(x,y-1)$ 、向右移动一格即抵达 $(x,y+1)$ 。

$\hspace{15pt}$ 现在，你位于迷宫的入口 $(0,0)$ ，想要前往终点 $(h-1,w-1)$ 。请输出一条从起点到终点的可行路径。

$\hspace{15pt}$ 保证起点和终点一定为空方格，你始终可以找到且能唯一找到一条从起点出发到达终点的可行路径。

输入描述:

第一行输入两个整数  代表迷宫的行数和列数。
此后  行，第  行输入  个整数  代表迷宫的布局。其中， 表示单元格  是空方格， 表示单元格  是墙方格。

输出描述:

输出若干行，第  行输出两个整数  ，表示路径的第  步抵达的单元格坐标为  。

你需要保证输出的路径是符合题目要求的，即从起点  出发，到达终点  ，且路径上每个单元格都是空方格，行走的单元格都是彼此相邻的。

示例1

输入

输出

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

示例2

输入

输出

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

算法知识视频讲解

Javascript

我最爱工作😝

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    const matrix=[];
    const hw = await readline();
    const [h,w] = hw.split(' ').map(v=>Number(v));
    while(line = await readline()){
        matrix.push(line.split(' ').map(v=>Number(v)))
    }
    //位置是否被访问过
    const visited = new Array(h).fill(false).map(()=>new Array(w).fill(false));
    const queue = [[0,0]];//设置当前待访问的节点队列，从0,0开始
    const paths = [];//记录访问路径
    const directions = [
        [-1,0],//向上
        [1,0],//向下
        [0,-1],//向左
        [0,1]//向右
    ]
    while(queue.length>0){
        const point = queue.shift();
        paths.push(point);
        if(point[0] === h -1 && point[1] === w - 1){
            //到终点就停止
            break;
        }
        for(let [dx, dy] of directions) {
            const nx = point[0] + dx;
            const ny = point[1] + dy;
            if(nx >= 0 && nx < h
                && ny >= 0 && ny < w
                && matrix[nx][ny] !== 1
                && !visited[nx][ny]) {
                    //没有越界，不是障碍且没被访问过
                    queue.push([nx,ny]);
                    visited[nx][ny] = true;
                }
        }
    }
    for(let i = paths.length - 1; i >=1; i--){
        //反向循环，删除死路，前一个节点不相邻即删除
        const isPreRight = directions.some(([dx,dy]) => {
            const newDire = [paths[i][0]+dx, paths[i][1]+dy];
            return newDire[0] === paths[i-1][0] && newDire[1] === paths[i-1][1]
        })
        if(!isPreRight){
            //前一个节点不对，删除掉它，然后当前节点的index变为了i-1
            //在下个循环中继续与它的前一个节点比较
            paths.splice(i - 1,1)
        }
    }
    for(let p of paths){
        console.log(`(${p[0]},${p[1]})`)
    }
}()

发表于 2025-02-28 08:15:28 回复(0)

Javascript

烦恼的打工人拒绝内卷

const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    const [N, M] = (await readline()).split(" ").map(Number);
    const matrix = [];
    let i = 0;
    while (i++ < N) {
        matrix.push((await readline()).split(" ").map(Number));
    }

    const [x, y] = [0, 0];
    let res = null;

    const recursion = (i, j, previousDirection, prevPath) => {
        if (res !== null) return;
        if (i < 0 || i >= N || j < 0 || j >= M) return;

        const path = [...prevPath];
        path.push(`(${i},${j})`);

        if (i === N - 1 && j === M - 1) return (res = path);

        // UP
        if (
            previousDirection !== "DOWN" &&
            i - 1 >= 0 &&
            matrix[i - 1][j] !== 1
        ) {
            recursion(i - 1, j, "UP", path);
        }
        // RIGHT
        if (
            previousDirection !== "LEFT" &&
            j + 1 < M &&
            matrix[i][j + 1] !== 1
        ) {
            recursion(i, j + 1, "RIGHT", path);
        }
        // DOWN
        if (previousDirection !== "UP" && i + 1 < N && matrix[i + 1][j] !== 1) {
            recursion(i + 1, j, "DOWN", path);
        }
        // LEFT
        if (
            previousDirection !== "RIGHT" &&
            j - 1 >= 0 &&
            matrix[i][j - 1] !== 1
        ) {
            recursion(i, j - 1, "LEFT", path);
        }
        return;
    };

    recursion(x, y, undefined, []);

    res.map((r) => console.log(r));
})();

编辑于 2024-02-26 14:31:30 回复(0)

Javascript

牛客670167887号

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
var flag=true,m,n,arr=[],res
function findWay(i,j,direction,path){
    if(i==m-1 && j==n-1){
        for(let i in path){
            console.log('('+path[i][0]+','+path[i][1]+')')
        }
    }
    if(i+1<m && arr[i+1][j]==0 && direction[1]!=0){
        findWay(i+1,j,[0,1,1,1],path.concat([[i+1,j]]))
    }
    if(i-1>=0 && arr[i-1][j]==0 && direction[0]!=0){
        findWay(i-1,j,[1,0,1,1],path.concat([[i-1,j]]))
    }
    if(j+1<n && arr[i][j+1]==0 && direction[3]!=0){
        findWay(i,j+1,[1,1,0,1],path.concat([[i,j+1]]))
    }
    if(j-1>=0 && arr[i][j-1]==0 && direction[2]!=0){
        findWay(i,j-1,[1,1,1,0],path.concat([[i,j-1]]))
    }
}
rl.on('line', function (line) {
    const tokens = line.split(' ');
    if (tokens[tokens.length-1]=='') tokens.pop()
    if(flag){
        m=parseInt(tokens[0]),n=parseInt(tokens[1])
        flag=false
    }
    else{
        arr.push(tokens.map((value,index,arr)=>{
            return parseInt(value)
        }))
        if(arr.length==m){
            //console.log(arr)
            findWay(0,0,[0,1,0,1],[[0,0]])
            arr=[]
            flag=true
        }
    }
});

js递归

发表于 2021-09-27 19:12:36 回复(0)

JavaScript

AD0N1S1

Node环境的解法来一个思路和其他语言的差不多

const readline = require('readline')
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
})
let N = 0
let M = 0
let arr = []
let Maze = []
let MazeResult = []
let count = 0
rl.on('line', line => {
  arr.push(line)
  if(arr.length == 1) {
    N = Number(arr[0].split(' ')[0])
    M = Number(arr[0].split(' ')[1])
  }
  if(arr.length == N+1) {
    Maze = arr.slice(1)
    Maze = Maze.map(item => {
       temp = item.split(' ')
      return temp
    })
    handleMaze(0, 0)
    MazeResult.forEach(item => {
      console.log(`(${item.row},${item.col})`)
    })
    N = 0
    M = 0
    arr = []
    Maze = []
    MazeResult = []
  }
})
 function handleMaze(row, col) {
    if (Maze[row][col] == 0) {
      MazeResult.push({row: row, col: col})
    }
    Maze[row][col] = 1
    if (row === N-1 && col === M-1) return
    if (col+1<M && Maze[row][col+1] == 0) { //right
      handleMaze(row, col+1)
    } else if (row+1<N && Maze[row+1][col] == 0) { //bottom
      handleMaze(row+1, col)
    } else if (col>=1&&Maze[row][col-1] == 0) { //left
      handleMaze(row, col-1)
    } else if (row>=1 && Maze[row-1][col] == 0) { //top
      handleMaze(row-1, col)
    } else { //noway
      MazeResult.pop()
      let pre = MazeResult.slice(-1)[0]
      handleMaze(pre.row, pre.col)
    }
  }

编辑于 2021-06-29 17:45:58 回复(0)