每日一题(980. 不同路径 III)-回溯

题目

980. 不同路径 III

题解思路

• 表格中值为1的为起始点
• 值为0 的是可以经过的点，但是只能经过一次
• 值为2 的是终点，
• 计算从起点到终点一共有多少种路径

---

• 计算出值为0的方格个数，同时找到起点位置
• 当位于终点时候且经过所有的方格为0的点 即为一种路径

代码

C++

class Solution {
public:int backtrack(int i, int j, int n, vector<array<int, 2>> dirs, vector<vector<int>>& grid, int rows, int cols){if (grid[i][j] == 2){if (n == 0) {return 1;}return 0; }int temp = grid[i][j];int res = 0;grid[i][j] = -1;for(auto &[dx, dy] : dirs){int nx = i + dx;int ny = j + dy;if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && (grid[nx][ny] == 0 || grid[nx][ny] == 2)){res += backtrack(nx, ny, n - 1, dirs, grid, rows, cols);}}grid[i][j] = temp;return res;}int uniquePathsIII(vector<vector<int>>& grid) {int rows = grid.size(), cols = grid[0].size();int si = 0, sj = 0, n = 0;vector<array<int, 2>> dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});for (int i = 0; i < rows; ++ i){for (int j = 0; j < cols; ++ j){if (grid[i][j] == 0){n++;}else if (grid[i][j] == 1){n++;si = i;sj = j;}}}return backtrack(si, sj, n, dirs, grid, rows, cols);}
};

Python

class Solution:def uniquePathsIII(self, grid: List[List[int]]) -> int:rows, cols = len(grid), len(grid[0])si, sj, n = 0, 0, 0for i in range(rows):for j in range(cols):if grid[i][j] == 0:n += 1elif grid[i][j] == 1:n += 1si, sj = i, j def backtrack(i, j, n):if grid[i][j] == 2:if n == 0:return 1return 0temp = grid[i][j]grid[i][j] = -1res = 0for nx, ny in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] in [0, 2]:res += backtrack(nx, ny, n - 1)grid[i][j] = tempreturn resreturn backtrack(si, sj, n)