数据结构java迷宫寻路

给定一个M行N列的迷宫图，其中 "0"表示可通路，"1"表示障碍物，无法通行。在迷宫中只允许在水平或上下四个方向的通路上行走，走过的位置不能重复走。

5行8列的迷宫如下：

0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
则从左上角（1，1）至右下角（5，8）的最短路径为：

1,1--》2,1--》2,2--》2,3--》3,3--》3,4--》3,5--》4,5--》5,5--》5,6--》5,7--》5,8

题目保证每个迷宫最多只有一条最短路径。

请输出该条最短路径，如果不存在任何通路，则输出"NO FOUND".

输入格式:
第一行，输入M和N值，表示迷宫行数和列数。

接着输入M行数值，其中，0表示通路，1表示障碍物。每列数值用空格符间隔。

接下来可能输入多组迷宫数据。

当输入M的值为-1时结束输入。

输出格式:
按行顺序输出路径的每个位置的行数和列数，如 x,y

如果不存在任何路径，则输出"NO FOUND".

每组迷宫寻路结果用换行符间隔。

输入样例:
在这里给出一组迷宫。例如：

8 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4
0 0 1 0
0 0 0 0
0 0 1 1
0 1 0 0
-1 -1
输出样例:
在这里给出相应的输出。例如：

1,1
2,1
3,1
4,1
5,1
5,2
5,3
6,3
6,4
6,5
7,5
8,5
8,6
8,7
8,8

想起之前看过一个A*寻路算法,来自：《漫画算法 - 小灰的算法之旅》，不纠结复杂度的话，可以直接用dfs四向查找。

//迷宫地图
public static final int[][] MAZE = {
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 1, 0, 0, 0 },
    { 0, 0, 0, 1, 0, 0, 0 },
    { 0, 0, 0, 1, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 }
};

/**
 * A*寻路主逻辑
 * @param start 迷宫起点
 * @param end 迷宫终点
 */
public static Grid aStarSearch(Grid start, Grid end) {
    ArrayList<Grid> openList = new ArrayList<Grid>();
    ArrayList<Grid> closeList = new ArrayList<Grid>();
    //把起点加入 openList
    openList.add(start);
    //主循环，每一轮检查1个当前方格节点
    while (openList.size() > 0) {
        // 在openList中查找 F值最小的节点，将其作为当前方格节点
        Grid currentGrid = findMinGird(openList);
        // 将当前方格节点从openList中移除
        openList.remove(currentGrid);
        // 当前方格节点进入 closeList
        closeList.add(currentGrid);
        // 找到所有邻近节点
        List<Grid> neighbors = findNeighbors(currentGrid, openList, closeList);
        for (Grid grid : neighbors) {
            if (!openList.contains(grid)) {
                //邻近节点不在openList中，标记“父节点”、G、H、F，并放入openList
                grid.initGrid(currentGrid, end);
                openList.add(grid);
            }
        }
        //如果终点在openList中，直接返回终点格子
        for (Grid grid : openList){
            if ((grid.x == end.x) && (grid.y == end.y)) {
                return grid;
            }
        }
    }
//openList用尽，仍然找不到终点，说明终点不可到达，返回空
return null;
}

private static Grid findMinGird(ArrayList<Grid> openList) {
    Grid tempGrid = openList.get(0);
    for (Grid grid : openList) {
        if (grid.f < tempGrid.f) {
            tempGrid = grid;
        }
    }
    return tempGrid;
}

private static ArrayList<Grid> findNeighbors(Grid grid, List<Grid> openList, List<Grid> closeList) {
    ArrayList<Grid> gridList = new ArrayList<Grid>();
    if (isValidGrid(grid.x, grid.y-1, openList, closeList)) {
        gridList.add(new Grid(grid.x, grid.y - 1));
    }
    if (isValidGrid(grid.x, grid.y+1, openList, closeList)) {
        gridList.add(new Grid(grid.x, grid.y + 1));
    }
    if (isValidGrid(grid.x-1, grid.y, openList, closeList)) {
        gridList.add(new Grid(grid.x - 1, grid.y));
    }
    if (isValidGrid(grid.x+1, grid.y, openList, closeList)) {
        gridList.add(new Grid(grid.x + 1, grid.y));
    }
    return gridList;
}

private static boolean isValidGrid(int x, int y, List<Grid> openList, List<Grid> closeList) {
    //是否超过边界
    if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length) {
        return false;
    }
    //是否有障碍物
    if(MAZE[x][y] == 1){
        return false;
    }
    //是否已经在openList中
    if(containGrid(openList, x, y)){
        return false;
    }
    //是否已经在closeList中
    if(containGrid(closeList, x, y)){
        return false;
    }
    return true;
}

private static boolean containGrid(List<Grid> grids, int x, int y) {
    for (Grid grid : grids) {
        if ((grid.x == x) && (grid.y == y)) {
            return true;
        }
    }
    return false;
}

tatic class Grid {
    public int x;
    public int y;
    public int f;
    public int g;
    public int h;
    public Grid parent;

    public Grid(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void initGrid(Grid parent, Grid end){
        this.parent = parent;
        if(parent != null){
            this.g = parent.g + 1;
        } else {
            this.g = 1;
        }
        this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
        this.f = this.g + this.h;
    }
}

public static void main(String[] args) {
    //设置起点和终点
    Grid startGrid = new Grid(2, 1);
    Grid endGrid = new Grid(2, 5);
    //搜索迷宫终点
    Grid resultGrid = aStarSearch(startGrid, endGrid);
    //回溯迷宫路径
    ArrayList<Grid> path = new ArrayList<Grid>();
    while (resultGrid != null) {
        path.add(new Grid(resultGrid.x, resultGrid.y));
        resultGrid = resultGrid.parent;
    }
    //输出迷宫和路径，路径用*表示
    for (int i = 0; i < MAZE.length; i++) {
        for (int j = 0; j < MAZE[0].length; j++) {
            if (containGrid(path, i, j)) {
                System.out.print("*, ");
            } else {
                System.out.print(MAZE[i][j] + ", ");
                }
            }
        System.out.println();
    }
}

作者：小灰
链接：https://leetcode-cn.com/leetbook/read/journey-of-algorithm/52thz6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。