980. Unique Paths III

Link: https://leetcode.com/problems/squares-of-a-sorted-array/

On a 2-dimensional grid, there are 4 types of squares:

• 1 represents the starting square. There is exactly one starting square.
• 2 represents the ending square. There is exactly one ending square.
• 0 represents empty squares we can walk over.
• -1 represents 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:

Input: [[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:

Input: [[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:

Input: [[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.

Note:

• 1 <= grid.length * grid[0].length <= 20

---

題目翻譯:

在二維網格上，有四種類型的正方形：

• 1 表示起始正方形。只有一個起始廣場。
• 2 表示結束方塊。只有一個結束方塊。
• 0 表示我們可以走過的空方塊。
• -1 表示我們無法走過的障礙。

返回從起始正方形到結束正方形的四向行走的數量，它在每個非障礙物正方形上行走一次。

程式思路:

到達 2 時 檢查路徑是否還有 0。 先往右，往下，往左，往上，使用遞迴，不算太難，但程式碼稍長。

class Solution {
public:
    bool IsAllPassed(vector<vector<int>> grid)
    {
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == 0)
                    return false;
            }
        }
        return true;
    }
    bool IsValid(int x, int y, int x_max, int y_max)
    {
        if (x >= 0 && x < x_max && y >= 0 && y < y_max)
        {
            return true;
        }
        return false;
    }

    void DFS(int &paths_num, vector<vector<int>> grid, int x, int y)
    {
        const int steps[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
        grid[x][y] = -1;
        for (int i = 0; i < 4; i++)
        {
        int next_x = x + steps[i][0];
        int next_y = y + steps[i][1];
        if (IsValid(next_x, next_y, grid.size(), grid[0].size()))
        {
        //printf(" (%d %d) -> (%d %d) = %d\n", x, y, next_x, next_y, grid[next_x][next_y]);
            if (grid[next_x][next_y] == -1)
                {
                    //continue;
                }
                else if (grid[next_x][next_y] == 0)
                {
                    DFS(paths_num, grid, next_x, next_y);
                }
                else if (grid[next_x][next_y] == 2)
                {
                    if (IsAllPassed(grid))
                        paths_num++;
                }
            }
        }
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
        int start_x = 0;
        int start_y = 0;
        int paths_num = 0;

        //find start point
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == 1)
                {
                    start_x = i;
                    start_y = j;
                    break;
                }
            }
        }
        DFS(paths_num, grid, start_x, start_y);
        return paths_num;
    }
};