LeetCode1091 最短路径 dfs bfs 递归 广度_leetcode 1091 dfs

测试用例

        System.out.println("= " + new test3().shortestPathBinaryMatrix(new int[][]{{0, 1, 0, 1, 0}, {1, 0, 0, 0, 1}, {0, 0, 1, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 0}}));
        System.out.println(" = " + new test3().shortestPathBinaryMatrix(new int[][]{{0, 0,0}, {1,1, 0},{1,1,0}}));
        System.out.println(" = " + new test3().shortestPathBinaryMatrix(new int[][]{{0, 0,0}, {0,0, 0},{0,0,0}}));
1
2
3

1 dfs

    //有回溯影响效率  计算超时
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        //记录
        boolean[][] visit = new boolean[grid.length][grid[0].length];
        return serarch(grid, visit, 0, 0) == 0 ? -1 : serarch(grid, visit, 0, 0);
    }

    public int serarch(int[][] grid, boolean[][] visit, int i, int j) {

        //条件判断
        if (grid[i][j] != 0) {
            return 0;
        }
        if (visit[i][j]) {
            return 0;
        }
        //临界值
        if (i == grid.length - 1 && grid[0].length - 1 == j) {
            return 1;
        }
        //记录此深度已近遍历的
        visit[i][j] = true;
        int[] ints = new int[8];
        if (i < grid.length - 1 && grid[i + 1][j] == 0) {
            ints[0] = serarch(grid, visit, i + 1, j);
        }
        if (j < grid[0].length - 1 && grid[i][j + 1] == 0) {
            ints[1] = serarch(grid, visit, i, j + 1);
        }
        if (i >= 1 && grid[i - 1][j] == 0) {
            ints[2] = serarch(grid, visit, i - 1, j);
        }
        if (j >= 1 && grid[i][j - 1] == 0) {
            ints[3] = serarch(grid, visit, i, j - 1);
        }
        if (i < grid.length - 1 && j < grid[0].length - 1 && grid[i + 1][j + 1] == 0) {
            ints[4] = serarch(grid, visit, i + 1, j + 1);
        }

        if (i < grid.length - 1 && j >= 1 && grid[i + 1][j - 1] == 0) {
            ints[5] = serarch(grid, visit, i + 1, j - 1);
        }
        if (j < grid.length - 1 && i >= 1 && grid[i - 1][j + 1] == 0) {
            ints[6] = serarch(grid, visit, i - 1, j + 1);
        }
        if (i >= 1 && j >= 1 && grid[i - 1][j - 1] == 0) {
            ints[7] = serarch(grid, visit, i - 1, j - 1);
        }
        //回退记录 回溯到上层 接着查找
        visit[i][j] = false;

        //找到8个方向中最短的一条
        int min = -2;
        for (int v : ints) {
            if (v > 0) {
                min = min == -2 ? v : Math.min(min, v);
            }
        }
        return min + 1;

    }
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

2 bfs

 public int serarch(int[][] grid) {

        if (grid.length == 0) {
            return 0;
        }
        if(grid[0][0] == 1){
            return -1;
        }

        //初始化一个队列
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.add(new Node(0, 0));
        grid[0][0] = 2;


        int[][] dir = {{1, -1}, {1, 0}, {1, 1}, {0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};

        int pat=0;
        while (!nodes.isEmpty()) {
            pat++;
            int nodeSize = nodes.size();
            //记录每一次广度遍历长度 用来记录层深度
            for (int q = 0; q < nodeSize; q++) {
                Node pop = nodes.pop();
                int i = pop.x;
                int j = pop.y;


                //8个方向
                if (i == grid.length - 1 && grid[0].length - 1 == j) {
                    return pat;
                }
//                if (i < grid.length - 1 && grid[i + 1][j] == 0) {
//                    nodes.add(new Node(i + 1, j));
//                    grid[i + 1][j] = 2;
//                }
//                if (j < grid[0].length - 1 && grid[i][j + 1] == 0) {
//                    nodes.add(new Node(i, j + 1));
//                    grid[i][j + 1] = 2;
//                }
//                if (i >= 1 && grid[i - 1][j] == 0) {
//                    nodes.add(new Node(i - 1, j));
//                    grid[i - 1][j] = 2;
//                }
//                if (j >= 1 && grid[i][j - 1] == 0) {
//                    nodes.add(new Node(i, j - 1));
//                    grid[i][j - 1] = 2;
//                }
//                if (i < grid.length - 1 && j < grid[0].length - 1 && grid[i + 1][j + 1] == 0) {
//                    nodes.add(new Node(i + 1, j + 1));
//                    grid[i + 1][j + 1] = 2;
//                }
//
//                if (i < grid.length - 1 && j >= 1 && grid[i + 1][j - 1] == 0) {
//                    nodes.add(new Node(i + 1, j - 1));
//                    grid[i + 1][j - 1] = 2;
//                }
//                if (j < grid.length - 1 && i >= 1 && grid[i - 1][j + 1] == 0) {
//                    nodes.add(new Node(i - 1, j + 1));
//                    grid[i - 1][j + 1] = 2;
//                }
//                if (i >= 1 && j >= 1 && grid[i - 1][j - 1] == 0) {
//                    nodes.add(new Node(i - 1, j - 1));
//                    grid[i - 1][j - 1] = 2;
//                }
                //8个方向  优化下

                for (int[] d : dir){
                    int x1 = i + d[0];
                    int y1 = j + d[1];
                    if (x1 < 0 || x1 >= grid.length || y1 < 0||y1>=grid[0].length || grid[x1][y1]==1){
                        continue;
                    }
                    nodes.add(new Node(x1, y1));
                    grid[x1][y1] = 2;
                }

            }

        }
        return -1;
    }


    class Node {
        int x;
        int y;

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

    }
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