featureLab/bitkylin-algorithm/section-9/leetcode9/UniquePathsIii.java at master · bitkylin/featureLab · GitHub

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/**
 * <p>在二维网格 <code>grid</code> 上，有 4 种类型的方格：</p>
 *
 * <ul>
 * <li><code>1</code> 表示起始方格。且只有一个起始方格。</li>
 * <li><code>2</code> 表示结束方格，且只有一个结束方格。</li>
 * <li><code>0</code> 表示我们可以走过的空方格。</li>
 * <li><code>-1</code> 表示我们无法跨越的障碍。</li>
 * </ul>
 *
 * <p>返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目<strong>。</strong></p>
 *
 * <p><strong>每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格</strong>。</p>
 *
 * <p>&nbsp;</p>
 *
 * <p><strong>示例 1：</strong></p>
 *
 * <pre><strong>输入：</strong>[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
 * <strong>输出：</strong>2
 * <strong>解释：</strong>我们有以下两条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
 * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)</pre>
 *
 * <p><strong>示例 2：</strong></p>
 *
 * <pre><strong>输入：</strong>[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
 * <strong>输出：</strong>4
 * <strong>解释：</strong>我们有以下四条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
 * 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
 * 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
 * 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)</pre>
 *
 * <p><strong>示例 3：</strong></p>
 *
 * <pre><strong>输入：</strong>[[0,1],[2,0]]
 * <strong>输出：</strong>0
 * <strong>解释：</strong>
 * 没有一条路能完全穿过每一个空的方格一次。
 * 请注意，起始和结束方格可以位于网格中的任意位置。
 * </pre>
 *
 * <p>&nbsp;</p>
 *
 * <p><strong>提示：</strong></p>
 *
 * <ul>
 * <li><code>1 &lt;= grid.length * grid[0].length &lt;= 20</code></li>
 * </ul>
 * <div><div>Related Topics</div><div><li>位运算</li><li>数组</li><li>回溯</li><li>矩阵</li></div></div><br><div><li>👍 176</li><li>👎 0</li></div>
 */

package leetcode9;

public class UniquePathsIii {

    public static void main(String[] args) {
        new UniquePathsIii().new Solution().uniquePathsIII(new int[][]{
                {1, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 2, -1}
        });
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * DFS + 回溯
     */
    class Solution {

        private final int[][] addr = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0},};

        public int uniquePathsIII(int[][] grid) {
            int count = 1;
            int[] start = null;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        start = new int[]{i, j};
                    }
                    if (grid[i][j] == 0) {
                        count++;
                    }
                }
            }
            grid[start[0]][start[1]] = 0;
            return solve(grid, start[0], start[1], count);
        }

        private int solve(int[][] grid, int x, int y, int count) {
            if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == -1) {
                return 0;
            }
            if (grid[x][y] == 2) {
                return count == 0 ? 1 : 0;
            }
            int res = 0;
            grid[x][y] = -1;
            for (int[] point : addr) {
                res += solve(grid, x + point[0], y + point[1], count - 1);
            }
            grid[x][y] = 0;
            return res;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

    /**
     * DFS + 回溯，换一种写法
     */
    class Solution2 {

        public int uniquePathsIII(int[][] grid) {
            // 当grid[i][j] == 2, stepNum++, 这里直接初始化为1
            int startX = 0, startY = 0, stepNum = 1;
            // 遍历获取起始位置和统计总步数
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        startY = i;
                        startX = j;
                        continue;
                    }
                    if (grid[i][j] == 0) stepNum++;
                }
            }

            return dfs(startX, startY, stepNum, grid);
        }


        public int dfs(int x, int y, int stepSur, int[][] grid) {
            //排除越界的情况和遇到障碍的情况
            if (x < 0 || x >= grid[0].length || y < 0 || y >= grid.length || grid[y][x] == -1) return 0;
            if (grid[y][x] == 2) return stepSur == 0 ? 1 : 0;
            grid[y][x] = -1;  //已走过的标记为障碍
            int res = 0;
            res += dfs(x - 1, y, stepSur - 1, grid);
            res += dfs(x + 1, y, stepSur - 1, grid);
            res += dfs(x, y - 1, stepSur - 1, grid);
            res += dfs(x, y + 1, stepSur - 1, grid);
            grid[y][x] = 0;  //dfs遍历完该位置为起始位置的情况后，置零，以不影响后面的dfs
            return res;
        }
    }

}