題目： LeetCode - 980. Unique Paths III

題目說明

給一個陣列代表二維地圖，1 代表起點，2 代表終點，0 代表可以經過，-1 代表無法經過，求有幾條不同的路徑可以從 1 走到 2 並且所有 0 都經過一次。

解題思路

使用 dfs 的概念，先找出 0 的數量及起點的座標，接著使用 dfs，從起點的座標開始，當經過 0 時將 n 加一，並將當前座標先設為 -1，在進入下一層 dfs，結束後將當前座標回復為 0，最後當走到 2 時，若 n 與 target 相等代表有一條達成條件的路徑。

參考解法

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
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid)
    {
        int x, y, target{};
        for(int i{}; i < grid.size(); ++i) for(int j{}; j < grid[0].size(); ++j)
        {
            if(!grid[i][j]) ++target;
            else if(grid[i][j] == 1) x = j, y = i;
        }
        return dfs(grid, x, y, 0, target);
    }

private:
    int dfs(vector<vector<int>>& grid, int x, int y, int n, int target)
    {
        if(x < 0 || x >= grid[0].size() || y < 0 || y >= grid.size() || grid[y][x] == -1) return 0;
        if(grid[y][x] == 2) return n == target;
        if(!grid[y][x]) ++n;
        grid[y][x] = -1;
        int tmp = dfs(grid, x + 1, y, n, target) + dfs(grid, x - 1, y, n, target) + dfs(grid, x, y + 1, n, target) + dfs(grid, x, y - 1, n, target);
        grid[y][x] = 0;
        return tmp;
    }
};