# CSPT21 Lecture 15
## [Unique Paths III](https://leetcode.com/problems/unique-paths-iii/)

class Solution:
    res = 0
    """
    Plan
    Do DFS from the starting cell and do a search to get to the goal cell.
    Once you are at the goal cell, check if every valid cell has been visited.
    If not all valid cells have been visited, backtrack and try another solution.
    Else, add that to numPathsFound
    """
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        startingPoint = self.findStartingPoint(grid)
        self.uniquePathsIIIHelper(grid, startingPoint[0], startingPoint[1])
        return self.res
        
    def uniquePathsIIIHelper(self, grid, x, y):
        width, height = len(grid[0]), len(grid)
        if x < 0 or y < 0 or x >= width or y >= height or grid[y][x] == -1:
            return
        if grid[y][x] == 2:
            for i in range(height):
                for j in range(width):
                    if grid[i][j] == 0:
                        return
            self.res += 1
            return
            
        grid[y][x] = -1
        self.uniquePathsIIIHelper(grid, x - 1, y)
        self.uniquePathsIIIHelper(grid, x + 1, y)
        self.uniquePathsIIIHelper(grid, x, y - 1)
        self.uniquePathsIIIHelper(grid, x, y + 1)
        grid[y][x] = 0
    
    def findStartingPoint(self, grid):
        for y in range(len(grid)):
            for x in range(len(grid[0])):
                if grid[y][x] == 1:
                    return (x, y)