980.Unique Paths III === ###### tags: `Hard`,`Array`,`Backtracking`,`Matrix`,`Bit Manipulation` [980. Unique Paths III](https://leetcode.com/problems/unique-paths-iii/) ### 題目描述 You are given an `m x n` integer array `grid` where `grid[i][j]` could be: * `1` representing the starting square. There is exactly one starting square. * `2` representing the ending square. There is exactly one ending square. * `0` representing empty squares we can walk over. * `-1` representing obstacles that we cannot walk over. Return *the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.* ### 範例 **Example 1:** ![](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 Explanation: We have the following two paths: 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) ``` **Example 2:** ![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique2.jpg) ``` Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]] Output: 4 Explanation: We have the following four paths: 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) ``` **Example 3:** ![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg) ``` Input: grid = [[0,1],[2,0]] Output: 0 Explanation: There is no path that walks over every empty square exactly once. Note that the starting and ending square can be anywhere in the grid. ``` **Constraints**: * `m` == `grid.length` * `n` == `grid[i].length` * 1 <= `m`, `n` <= 20 * 1 <= `m` * `n` <= 20 * -1 <= `grid[i][j]` <= 2 * There is exactly one starting cell and one ending cell. ### 解答 ```python= class Solution: def uniquePathsIII(self, grid: List[List[int]]) -> int: def valid(x,y): if x>=0 and x<self.m and y>=0 and y<self.n: return True return False def dfs( node,step): x, y = node[0],node[1] if grid[x][y] == -1: return 0 elif grid[x][y] == 0 or grid[x][y] == 1: for dx,dy in [ (-1,0), (1,0), (0,-1), (0,1)]: if valid(x+dx, y+dy) and self.visit[x+dx][y+dy]==0: self.visit[x+dx][y+dy] = step dfs( (x+dx, y+dy), step+1) self.visit[x+dx][y+dy] = 0 elif grid[x][y] == 2 and step == self.m*self.n - self.rock_cnt + 1: self.ans += 1 '''for line in self.visit: for item in line: print(item, end=' ') print('') print('---')''' self.m, self.n = len(grid), len(grid[0]) self.visit = [ [0]*self.n for _ in range(self.m) ] self.ans = 0 self.rock_cnt = 0 for i in range(self.m): for j in range(self.n): if grid[i][j] == 1: begin = (i,j) self.visit[i][j] = 1 elif grid[i][j] == -1: self.rock_cnt += 1 #print(begin) dfs(begin, 2) return self.ans ``` > [name=玉山] #### Javascript ```javascript= function uiquePathIII(grid) { const start = []; let empty = 0; for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[i].length; j++) { if (grid[i][j] === 0) { empty++; } else if (grid[i][j] === 1) { start.push(i, j); } } } grid[start[0]][start[1]] = -1; return dfs(grid, start[0], start[1], empty); } // 遍歷所有可能的路徑,當遇到2時且剛好空格為0時,代表找到一條路徑 function dfs(grid, x, y, empty) { const isInBounds = (x, y, xLength, yLength) => x < xLength && x >= 0 && y < yLength && y >= 0; const neighbors = [ [x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1], ]; let total = 0; for (const [nx, ny] of neighbors) { if (!isInBounds(nx, ny, grid.length, grid[0].length)) continue; if (grid[nx][ny] === -1) continue; if (grid[nx][ny] === 2) { if (empty === 0) total++; continue; } grid[nx][ny] = -1; total += dfs(grid, nx, ny, empty - 1); grid[nx][ny] = 0; } return total; } ``` > 暴力解超級慢,不知道是不是題目想要的,但暫時沒想到更好的做法。 > [name=Marsgoat][time=Feb 22, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)