java迷宫寻找最短路径

利用广度优先遍历算法的特点，由于迷宫每次只能走一格，所以对于任意一个节点，bfs第一次到达该点时一定是最短路径

直接上代码：

package com.common.utils;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @ClassName Calculator
 * @Description:  java迷宫寻找最短路径
 * @Author: mischen
 * @date: 14:57 2022/11/24
 * @Version 1.0
 */
public class Maze {
    private class Node{
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private int[][] map;
    //起点
    private int startX;
    private int startY;
    //终点
    private int endX;
    private int endY;
    //代表上下左右四个可能走的方向
    private int[] dx = {1,0,-1,0};
    private int[] dy = {0,1,0,-1};
    public Maze(int[][] map, int startX, int startY, int endX, int endY) {
        this.map = map;
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
    }
    public static void print(int[][] map) {
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                System.out.printf("%4d",map[i][j]);
            }
            System.out.println();
        }
    }
    //广度优先遍历寻找迷宫所有点的最短路径， x,y是起始点
    public void bfs() {
        Deque<Node> quene = new ArrayDeque<>();
        //存储每个点的前驱节点，方便打印最短路径的路线
        int[][] pre = new  int[this.map.length][this.map[0].length];
        //存储每个点的最短路径
        int[][] dis = new  int[this.map.length][this.map[0].length];
        for(int i=0; i<dis.length; i++) {
            for(int j=0; j<dis[0].length; j++) {
                dis[i][j] = 100;
            }
        }
        //将起点入队，起点的距离设为0，并标记为已访问
        quene.add(new Node(this.startX, this.startY));
        dis[this.startX][this.startY] = 0;
        map[this.startX][this.startY] = 2;
        Node temp;
        //广度优先遍历所有可访问的点，并记下每个点的最短路径和前驱节点
        while(!quene.isEmpty()) {
            temp = quene.poll();
            //尝试每个点的四个方向
            for(int i=0; i<4; i++) {
                int tx = temp.x + dx[i];
                int ty = temp.y + dy[i];
                //如果该点没有访问过，将该点入队并标记为访问过
                if(map[tx][ty] == 0) {
                    //迷宫中每次只能走一步，所以距离加一
                    dis[tx][ty] = dis[temp.x][temp.y] + 1;
                    pre[tx][ty] = i;
                    map[tx][ty] = 2;
                    quene.add(new Node(tx, ty));
                }
            }
        }//到这里dis中存放的就是最短路径，下面时利用pre数组打印路径

        int a = this.endX;
        int b = this.endY;
        System.out.printf("从(%d,%d)到(%d,%d)的最短距离是：%d，路线为：\n",
                this.startX, this.startY, a, b, dis[a][b]);
        //倒序访问最短路径的路线并入栈
        Stack<Node> stack = new Stack<>();
        stack.add(new Node(a, b));
        while(a != this.startX || b != this.startY) {
            int da = dx[pre[a][b]];
            int db = dy[pre[a][b]];
            a = a - da;
            b = b - db;
            stack.add(new Node(a,b));
        }
        //出栈的顺序就是从起点到终点的路线
        while(!stack.isEmpty()) {
            Node p = stack.pop();
            System.out.printf("(%d,%d)->",p.x,p.y);
        }
    }
    public static void main(String[] args) {
        //创建一个迷宫并初始化
        int[][] map = new int[8][8];
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                map[i][j] = 0;
            }
        }
        for(int i=0; i<map.length; i++) {
            map[i][0] = -1;
            map[i][7] = -1;
            map[0][i] = -1;
            map[7][i] = -1;
        }
        map[4][1] = -1;
        map[4][2] = -1;
        map[5][3] = -1;
        map[4][4] = -1;
        map[3][4] = -1;

        print(map);
        Maze maze = new Maze(map, 1, 1, 5, 2);
        maze.bfs();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

运行结果：
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 -1 0 0 -1
-1 -1 -1 0 -1 0 0 -1
-1 0 0 -1 0 0 0 -1
-1 0 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1 -1
从(1,1)到(5,2)的最短距离是：13，路线为：
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(6,5)->(6,4)->(6,3)->(6,2)->(5,2)->