问题描述：假设有如下迷宫，求解从某一点出发到目标位置的最短距离

迷宫

Input: 5 4 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 4 3

Output: 7

深度优先搜索（DFS）

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
import java.util.Scanner;

public class DFS {
    static int[][] a = new int[51][51];
    static int[][] book = new int[51][51];
    static int n, m, p, q, min = 99999999;
    static int sum = 1;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = input.nextInt();
            }
        }
        int startX = input.nextInt();
        int startY = input.nextInt();
        p = input.nextInt();
        q = input.nextInt();
        book[startX][startY] = 1;
        
        dfs(startX,startY,0);

        System.out.println(min);

    }

    public static void dfs(int x, int y, int step) {
        /**
         * 按照右，下，左，上的顺时针顺序遍历
         * 定义一个方向数组，便于操作
         * */
        int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int tx, ty;
        /**
         * 是否到达目标位置，更新最小值
         * */
        if (x == p && y == q) {
            min = min < step ? min : step;
            return;
        }

        /**
         * 计算下个点的坐标
         * */
        for (int i = 0; i < 4; i++) {
            tx = x + next[i][0];
            ty = y + next[i][1];
            /**
             * 检查临界
             * */
            if (tx < 1 || tx > n || ty < 1 || ty > m) {
                continue;
            }
            /**
             * 不是障碍物，也未加入路径中，则执行dfs，注意回溯
             * */
            if (a[tx][ty] == 0 && book[tx][ty] == 0) {
                book[tx][ty] = 1;
                dfs(tx, ty, step + 1);
                /**
                 * 为了找到最短的路径必须进行回溯
                 * */
                book[tx][ty] = 0;
            }
        }
    }
}

同样的广度优先搜索（BFS）也可以接这个题目，但是要注意广度优先搜索需要有一个队列Queue来控制。这里需要创建一个Point类来保存坐标和距离。 另外，由于java本身没有提供队列获取队尾元素的api，所以在下面的算法中需要注意处理，方法不唯一。

广度优先搜索（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
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point{
    public int x;
    public int y;
    public int s;
    Point(int x, int y, int s) {
        this.x = x;
        this.y = y;
        this.s = s;
    }
}

public class BFS {
    static int[][] a = new int[51][51];
    static int[][] book = new int[51][51];
    static Queue<Point> queue = new LinkedList<>();
    static int n, m, p, q;
    static int min = 99999999;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = input.nextInt();
            }
        }
        int startX = input.nextInt();
        int startY = input.nextInt();
        p = input.nextInt();
        q = input.nextInt();
        queue.add(new Point(startX, startY, 0));
        book[startX][startY] = 1;

        bfs();

        System.out.println(min);
    }

    public static void bfs() {
        /**
         * 按照右，下，左，上的顺时针顺序遍历
         * 定义一个方向数组，便于操作
         * */
        int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int tx, ty;
        int flag = 0;

        while (!queue.isEmpty()) {
            for (int i = 0; i < 4; i++) {
                tx = queue.peek().x + next[i][0];
                ty = queue.peek().y + next[i][1];
                /**
                 * 临界条件
                 * */
                if (tx < 1 || tx > n || ty < 1 || ty > m) {
                    continue;
                }
                /**
                 * 非障碍物，未标记为1，则进行入队操作
                 * */
                if (a[tx][ty] == 0 && book[tx][ty] == 0) {
                   /**
                    * 标记为已拓展，不同于DFS的是，BFS每个点只会被拓展一次，无需进行回溯
                    * */
                   min = queue.peek().s + 1;
                    book[tx][ty] = 1;
                    queue.add(new Point(tx, ty, min));
                }

                if (tx == p && ty == q) {
                    flag = 1;
                    break;
                }
            }

            if (flag == 1) {
                /**
                 * 这里要注意的是，每次拓展完，且未到达目标位置时都会移出队首元素一次，
                 * 但是最后一次队列中至少存在两个元素，即正在处理的点，和这个点拓展到的目标
                 * 而直接出队操作是做不到的（即使将出队操作提前也不能实现），而且，
                 * 当大于两个点的时候，一次出队也不能起到实质性的作用
                 * 所以在这里我们在上个判断中直接改变全局变量mark的值即可实现
                 * */
                break;
            }
            queue.remove();
        }
    }
}