使用栈解决迷宫问题(深度优先遍历)

2019-10-06  本文已影响0人  好学人

问题描述:

有如图所示迷宫,设计一个算法,找出一条从入口到出口的路径。

思路分析:

  1. 我们使用一个二维数组模拟迷宫,并新建一个栈来保存从入口通往出口的路径。

  2. 然后以入口节点为基准节点依次向四周探测,如果探测到新的活节点,就将新探测到的活节点压入栈中,并以此新节点为基准节点继续向四周探测,直到找出迷宫出口。

  3. 如果某基准节点四周不存在活节点,则认为此基准节点为死节点,将其从栈中弹出,返回上次基准节点继续探测(为避免重复探测,探测过的基准节点要加上标记)。

详细步骤如下:

  1. 使用二维数组来模拟迷宫模型。
  2. 新建一个栈,用来保存迷宫的探索路径。
  3. 同时将入口节点标记为已探索并压入栈中。
  4. 以栈顶节点为基准节点向四周节点探索。
  5. 如果能探索到新的活节点,则标记后加入栈中,返回步骤 3。
  6. 如果探索不到新的活节点,说明此路不通,则弹出栈顶节点,然后返回步骤 3。
  7. 如果在找到出口,则成功退出;如果中途栈为空了,说明找不到路径,失败退出。

代码实现:

  1. 使用二维数据模拟迷宫:
public int[][] maze = {
        {1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 1, 1, 1},
        {1, 1, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 1, 1},
        {1, 0, 1, 1, 1, 0, 1, 1},
        {1, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1},
};
  1. 使用int[2]保存迷宫的坐标
迷宫入口:int[] start = {1, 1}
迷宫出口:int[] end = {6, 6}
  1. 在迷宫中进行深度优先搜索
/**
 * 在迷宫中进行深度优先搜索,搜索完成后栈中即为迷宫的一条可达路径
 */
public void searchPath(int[][] maze, int[] start, int[] end) {
    // 创建一个栈保存迷宫路径
    Stack<int[]> stack = new Stack<>();
    // 将迷宫入口位置压入栈中
    maze[start[0]][start[1]] = 2;
    stack.push(start);
    while (true) {
        if (stack.size() == 0) {
            System.out.println("搜索失败,未找到路径!");
            break;
        }
        // 以栈顶节点为基准节点向四周搜索
        int[] point = stack.peek();
        int x = point[0];
        int y = point[1];
        maze[x][y] = 2; // 将基准节点标记为已搜索
        if (x == end[0] && y == end[1]) {
            System.out.printf("搜索成功,找到出口(%d,%d)\n", x, y);
            break;
        }
        System.out.printf("正在探测(%d,%d)\n", x, y);
        // 向上搜索
        if (maze[x + 1][y] == 0) {
            stack.push(new int[]{x + 1, y});
            continue;
        }
        // 向下搜索
        if (maze[x - 1][y] == 0) {
            stack.push(new int[]{x - 1, y});
            continue;
        }
        // 向左搜索
        if (maze[x][y - 1] == 0) {
            stack.push(new int[]{x, y - 1});
            continue;
        }
        // 向右搜索
        if (maze[x][y + 1] == 0) {
            stack.push(new int[]{x, y + 1});
            continue;
        }
        // 上下左右都搜索不到活节点
        maze[x][y] = 3; // 标记为死节点
        stack.pop(); // 从栈顶弹出
    }
}
  1. 逆序输出栈中的元素
/**
 * 打印迷宫路径
 */
public void printStack(Stack<int[]> stack) {
    if (stack.size() > 0) {
        int[] point = stack.pop();
        printStack(stack);
        System.out.printf("(%d,%d)", point[0], point[1]);
    }
}

总结:

关于迷宫问题,可以使用递归解决,也可以通过栈解决,因为递归的底层也是栈结构。

但使用栈解决更有优势,因为不用担心方法调用栈溢出的问题。所以,以后涉及到递归的问题,都可以考虑使用栈来解决。

上一篇 下一篇

猜你喜欢

热点阅读