Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2022/12/31 14:46)推噓4(4推 0噓 3→)

留言7則, 7人參與討論串169/719 (看更多)

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