目录

迷宫路径(回溯+递归)

lienhui68 收录于技术

2020-06-12 约 635 字预计阅读 2 分钟次阅读

目录

介绍

如下图展示的一个迷宫，其中#表示墙，F表示出口，在迷宫中使用数字(1,2,3,4…)表示走过的一条路径

分析问题

我们可以采用回溯+递归的方法处理这类问题，从起始坐标开始向上下左右4个方向递归(已遍历过的坐标且没找到出口标记为B，表示此路不通)，如果没找到出口则回溯到该坐标另一个方向继续递归。

代码实现

 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


package com.eh.ftd.dsa.ds.impl;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/18 18:42
 */
public class Maze {

    static int n;

    /**
     * # 挡板
     * F 出口
     * R 通行路线中的点
     * B 不可通行
     */
    char[][] maze = {
            {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
            {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', 'F', '#'},
            {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
            {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
            {'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
            {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
            {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
            {'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
            {'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
    };


    /**
     * 寻找迷宫出口并打印路径
     * 按照下->右->左->上的策略进行回溯和递归
     *
     * @param x
     * @param y
     * @return
     */
    public boolean findMazePath(int x, int y) {

        if (maze[x][y] == 'F') {
            // 已找到
            return true;
        } else if (maze[x][y] == ' ') { // 因为4个方向试探，不允许往源头回溯
            // 还未通行
            maze[x][y] = (char) (++n % 10 + 48);
            // 四个方向试探
            if (findMazePath(x + 1, y) || findMazePath(x, y + 1) || findMazePath(x, y - 1) || findMazePath(x - 1, y)) {
                return true;
            } else {
                n--;
                maze[x][y] = 'B';
                return false;
            }
        }
        return false;
    }

    private void displayMazePath() {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Maze maze = new Maze();
        maze.findMazePath(1, 1);
        maze.displayMazePath();
    }
}

运行结果