# CSPT13 Build Week 4
## [Unique Paths III](https://leetcode.com/problems/unique-paths-iii/)

from typing import List

class Solution:
    res = 0

    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        startingPoint = self.findStartingPoint(grid)
        if startingPoint == None:
            return 0
        self.uniquePathsHelper(grid, startingPoint[0], startingPoint[1])
        return self.res

    def uniquePathsHelper(self, grid: List[List[int]], x: int, y: int):
        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.uniquePathsHelper(grid, x + 1, y)
        self.uniquePathsHelper(grid, x - 1, y)
        self.uniquePathsHelper(grid, x, y + 1)
        self.uniquePathsHelper(grid, x, y - 1)
        grid[y][x] = 0

    def findStartingPoint(self, grid: List[List[int]]):
        for y in range(len(grid)):
            for x in range(len(grid[0])):
                if grid[y][x] == 1:
                    return (x, y)
        return None