推 sustainer123: 大師 12/31 14:46
推 pandix: 大師 12/31 14:47
→ sixB: 不能走重複的格子ㄇ 12/31 14:50
→ Rushia: 走重複的格子會有無限組解欸 12/31 14:52
→ SecondRun: 今天的有點難== 12/31 14:58
推 NTHUlagka: 大師 12/31 15:32
推 AyuniD: 都忘記這樣就是窮舉了 害我還想要怎麼走所有可能的路線 12/31 17:44
980. Unique Paths III
有個機器人在一個迷宮裡面，這個迷宮有些地方有障礙物，他想要從起點走到終點並
且所有可以走的地方都要走過，找出共有幾種走法。
0：可以走
1：起點
2：終點
-1：障礙物
Example：
https://assets.leetcode.com/uploads/2021/08/02/lc-unique1.jpg
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
有兩種走法
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)
https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg
Input: grid = [[0,1],[2,0]]
Output: 0
有0種走法，沒辦法走過所有地方後停在終點
思路：
1.求出所有可能的路徑 --> 回溯法
2.先遍歷一次整個矩陣找出"起點座標"和"可以走的格子數量"
3.我們令3表示該格已經走過，省去宣告一個visited，然後對四個方向做dfs，當
下列情況時做剪枝：
(1)超出邊界
(2)碰到障礙物
(3)這格已經走過
4.每次走到可以走的格子時，"可以走的格子"數量減一。
5.當走到終點時（gird[i][j] == 2），如果可以走的格子數量等於0表示每個地方除
了障礙物和起點終點我們都走過，count + 1。
6.返回count。
Java Code：
-------------------------
class Solution {
public int uniquePathsIII(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] start = new int[2];
int squares = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
start[0] = i;
start[1] = j;
} else if (grid[i][j] == 0) {
squares++;
}
}
}
return dfs(grid, start[0], start[1], squares);
}
private final static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int dfs(int[][] grid, int i, int j, int squares) {
int m = grid.length;
int n = grid[0].length;
if (i == m || j == n || i < 0 || j < 0 || grid[i][j] == -1 ||
grid[i][j] == 3) {
return 0;
}
if (grid[i][j] == 0) {
squares--;
}
if (grid[i][j] == 2) {
return (squares == 0) ? 1 : 0;
}
int count = 0;
for (int[] dir : dirs) {
int tmp = grid[i][j];
grid[i][j] = 3;
count += dfs(grid,i + dir[0], j + dir[1], squares);
grid[i][j] = tmp;
}
return count;
}
}
-------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672469172.A.5E1.html