LC980 Unique Paths III

class Solution:
# main idea: count all the cells which are == 0, then get the coordinate x,y; try four directions until  reached to grid[i][j] == 2 ; check if cnt has been decresed to 0, if yes, path increament by 1 
# time O(3^(N-1))  space O(N) beceuse of stack recursion depth
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        cnt = 1 # cnt initialize as 1 because start point 
        self.res = 0
        x= y = -2
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    x,y = i,j
                if grid[i][j] == 0:
                    cnt += 1
        dir = [(-1,0),(1,0),(0,-1),(0,1)]
        def dfs(x,y,cnt):
            if not (0 <= x < row and 0 <= y <col and grid[x][y]>=0 ):
                return
            if grid[x][y] == 2:
                if cnt == 0:
                self.res += 1
                return 
            grid[x][y] = -2
            # optimization:  directly +1  -1 at the argument instead if referring direction indexing 
            for di in dir:
                dfs(x+di[0],y+di[1],cnt-1)
            grid[x][y] = 0
        dfs(x,y,cnt)
        return self.res