迷宫寻路

我被困在一个迷宫中

迷宫寻路

题目描述

你被困在一个 4x4 的迷宫中，迷宫的结构如下所示：

-----------------
| M | N | O | P |
-----------------
| I | J | K | L |
-----------------
| E | F | G | H |
-----------------
| A | B | C | D |
-----------------

迷宫中存在以下墙壁：

• M 和 N 之间有墙
• N 和 O 之间有墙
• J 和 K 之间有墙
• F 和 G 之间有墙
• I 和 E 之间有墙
• E 和 F 之间有墙
• K 和 G 之间有墙
• P 和 L 之间有墙

你的任务是从起点 P 出发，找到一条通往终点 A 的路径。在寻路过程中，你需要按照 北（N）、西（W）、南（S）、东（E） 的优先级进行移动。

问题

1. 列举当前经过的位置：请按照你的寻路顺序，列出从 P 到 A 所经过的所有位置。
2. 实现目标需要多少步：计算从 P 到 A 所需的总步数。
3. 需要多少个回溯步骤：在寻路过程中，如果遇到死胡同，你需要回溯到上一个分叉点。请计算总共需要回溯多少次。
4. 使用 Java 模拟：编写一个 Java 程序，模拟从 P 到 A 的寻路过程，并输出经过的位置、总步数和回溯次数。具体实现过程由你自由发挥，只需要确保输出结果正确即可。

提示

• 在移动时，优先尝试向北（N）移动，如果不行则依次尝试西（W）、南（S）、东（E）。
• 注意墙壁的存在，确保不会穿过墙壁。
• 回溯步骤是指在遇到死胡同时，需要返回到上一个可以继续探索的位置。

示例

假设迷宫中不存在墙壁，从 P 到 A 的路径可能是：P → L → H → D → C → B → A。但在这个迷宫中，由于墙壁的存在，路径会有所不同。

解答要求

请详细描述你的寻路过程，并回答上述三个问题。同时，编写一个 Java 程序来模拟寻路过程，并输出结果。

预期输出

枚举表应该类似如下内容：

No.	Curr	N	W	S	E	Back
1	P	Blocked	OK
2	O	Blocked	Blocked	OK
…	…	…	…	…	…	…
20	A

程序应输出类似以下内容：

经过的位置: [P, O, N, M, I, J, F, E, A]
总步数: 9
回溯次数: 2

参考答案

No.	Curr	N	W	S	E	Back
1	P	Blocked	OK
2	O	Blocked	Blocked	OK
3	K	Visited	Blocked	Blocked	OK
4	L	Blocked	Visited	OK
5	H	Visited	OK
6	G	Blocked	Blocked	OK
7	C	Visited	OK
8	B	OK
9	F	OK
10	J	OK
11	N	Blocked	Blocked	Visited	Blocked	Back
12	J	Used	OK
13	I	OK
14	M	Blocked	Blocked	Visited	Blocked	Back
15	I	Used	Blocked	Blocked	Visited	Back
16	J	Used	Used	Visited	Blocked	Back
17	F	Used	Blocked	Visited	Blocked	Back
18	B	Used	OK
19	A

P > O > K > L > H > G > C > B > A.
8 Steps shortest.
5 back steps.
18 total steps.

import java.util.*;

public class Main {
    private static final char[][] MAZE = {
        {'M', 'N', 'O', 'P'},
        {'I', 'J', 'K', 'L'},
        {'E', 'F', 'G', 'H'},
        {'A', 'B', 'C', 'D'}
    };
    
    private static final Map<Character, Set<Character>> WALLS = new HashMap<>();
    private static final List<Character> path = new ArrayList<>();
    private static int backSteps = 0;
    private static Set<Character> visited = new HashSet<>();
    
    static {
        addWall('M', 'N');
        addWall('N', 'O');
        addWall('J', 'K');
        addWall('F', 'G');
        addWall('I', 'E');
        addWall('E', 'F');
        addWall('K', 'G');
        addWall('P', 'L');
    }
    
    private static void addWall(char a, char b) {
        WALLS.computeIfAbsent(a, k -> new HashSet<>()).add(b);
        WALLS.computeIfAbsent(b, k -> new HashSet<>()).add(a);
    }
    
    private static boolean hasWall(char from, char to) {
        return WALLS.getOrDefault(from, Collections.emptySet()).contains(to);
    }
    
    private static List<Character> getNeighbors(char current) {
        int[] pos = findPosition(current);
        int row = pos[0], col = pos[1];
        List<Character> neighbors = new ArrayList<>();
        
        // North
        if (row > 0 && !hasWall(current, MAZE[row-1][col])) 
            neighbors.add(MAZE[row-1][col]);
        // West
        if (col > 0 && !hasWall(current, MAZE[row][col-1])) 
            neighbors.add(MAZE[row][col-1]);
        // South
        if (row < 3 && !hasWall(current, MAZE[row+1][col])) 
            neighbors.add(MAZE[row+1][col]);
        // East
        if (col < 3 && !hasWall(current, MAZE[row][col+1])) 
            neighbors.add(MAZE[row][col+1]);
            
        return neighbors;
    }
    
    private static int[] findPosition(char c) {
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (MAZE[i][j] == c)
                    return new int[]{i, j};
        return null;
    }
    
    private static boolean dfs(char current, char target) {
        path.add(current);
        visited.add(current);
        
        if (current == target) return true;
        
        for (char next : getNeighbors(current)) {
            if (!visited.contains(next)) {
                if (dfs(next, target)) return true;
                backSteps++;
            }
        }
        
        path.remove(path.size() - 1);
        return false;
    }
    
    public static void main(String[] args) {
        dfs('P', 'A');
        
        System.out.println("经过的位置: " + path);
        System.out.println("总步数: " + (path.size() - 1));
        System.out.println("回溯次数: " + backSteps);
    }
}