首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路

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

假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙

输入描述:

迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。

输出描述:

路径的长度，是一个整数

示例1

输入

输出

算法知识视频讲解

Java

SongWindLuo

import java.util.*;

class Node {
    int x, y, keys, steps;

    public Node(int x, int y, int keys, int steps) {
        this.x = x;
        this.y = y;
        this.keys = keys;
        this.steps = steps;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static int m, n;
    public static char[][] maze;    
    public static int[][][] visited; //保存是否已经计算过
    public static int[] dirX = {0, 0, 1, -1};
    public static int[] dirY = {1, -1, 0, 0};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        n = in.nextInt();
        in.nextLine();
        maze = new char[m][n];

        visited = new int[m][n][1024];

        for (int i = 0; i < m; i++) {
            String str = in.nextLine();
            //in.nextLine();
            maze[i] = str.toCharArray();

            //System.out.println(maze[i]);
        }



        int ans = -1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] == '2') {
                    visited[i][j][0] = 1;
                    ans = bfs(i, j);
                    break;
                }
            }
        }
        System.out.println(ans);
    }

    public static int bfs(int i, int j) {
        Queue<Node> q = new LinkedList<>();
        //将入口加入队列，没钥匙，0步
        q.add(new Node(i, j, 0, 0));

        while (!q.isEmpty()) {
            Node node = q.poll();
            //下面特别注意当前点是node.x,node.y，不是i,j
            if (maze[node.x][node.y] == '3') {
                //到达出口，退出
                return node.steps;
            }
            //4个方向扩散
            for (int d = 0; d < 4; d++) {
                int newX = node.x + dirX[d];
                int newY = node.y + dirY[d];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                    int key = node.keys;
                    if (maze[newX][newY] == '0') {
                        continue;
                    }
                    //遇到钥匙，增加新钥匙
                    if (maze[newX][newY] >= 'a' && maze[newX][newY] <= 'z') {
                        key = key | (1 << (maze[newX][newY] - 'a'));
                    }
                    //遇到门，且当前钥匙串没有对应钥匙，结束
                    if (maze[newX][newY] >= 'A' && maze[newX][newY] <= 'Z'
                            && (key & (1 << (maze[newX][newY] - 'A'))) == 0) {
                        continue;
                    }
                    //剩下是可通过情形
                    if (visited[newX][newY][key] == 0) {
                        visited[newX][newY][key] = 1;
                        q.add(new Node(newX, newY, key, node.steps + 1));
                    }
                }
            }
        }

        return 0;
    }
}

发表于 2025-01-21 21:02:30 回复(0)