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

Difficulty: interview

Starter code:

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def fun(g,i0,i1,n1,t1,f2,row,col):
            if n1==t1:
                if abs(f2[1]-i1)+abs(f2[0]-i0)==1:
                    self.ans+=1
            else:
                if i1+1!=col and g[i0][i1+1]==0:
                    g[i0][i1+1]=1
                    fun(g,i0,i1+1,n1+1,t1,f2,row,col)
                    g[i0][i1+1]=0
                if i1!=0 and g[i0][i1-1]==0:
                    g[i0][i1-1]=1
                    fun(g,i0,i1-1,n1+1,t1,f2,row,col)
                    g[i0][i1-1]=0
                if i0+1!=row and g[i0+1][i1]==0:
                    g[i0+1][i1]=1
                    fun(g,i0+1,i1,n1+1,t1,f2,row,col)
                    g[i0+1][i1]=0
                if i0!=0 and g[i0-1][i1]==0:
                    g[i0-1][i1]=1
                    fun(g,i0-1,i1,n1+1,t1,f2,row,col)
                    g[i0-1][i1]=0
        
        self.ans=0
        i0,i1,t1=0,0,0
        f2=[0,0]
        row = len(grid)
        col = len(grid[0])
        for i in range(row):
            for j in range(col):
                if grid[i][j]==0:
                    t1+=1
                elif grid[i][j]==1:
                    i0,i1 = i,j
                elif grid[i][j]==2:
                    f2 = [i,j]
        fun(grid,i0,i1,0,t1,f2,row,col)
        return self.ans

class Solution:
    def uniquePathsIII(self, grid):

        maxPath = 2
        neighbors = [None] * (len(grid) * len(grid[0]))
        visited = [False] * (len(grid) * len(grid[0]))
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                node = x*len(grid[0]) + y
                if grid[x][y] == 0:
                    neighbors[node] = getNeighbors(grid, x, y)
                    visited[node] = False
                    maxPath += 1
                elif grid[x][y] == 1:
                    start = node
                    neighbors[node] = getNeighbors(grid, x, y)
                elif grid[x][y] == 2:
                    end = node
                    visited[node] = False

        return count(neighbors, visited, start, maxPath, 1, end)

def getNeighbors(grid, x, y):
    output = []
    if x > 0 and grid[x-1][y] % 2 == 0:
        output.append((x-1)*len(grid[0])+y)
    if x < len(grid)-1 and grid[x+1][y] % 2 == 0:
        output.append((x+1)*len(grid[0])+y)
    if y > 0 and grid[x][y-1] % 2 == 0:
        output.append(x*len(grid[0])+y-1)
    if y < len(grid[0]) - 1 and grid[x][y+1] % 2 == 0:
        output.append(x*len(grid[0])+y+1)
    return output
    
def count(neighbors, visited, node, maxPath, pathLength, destination):

    if pathLength == maxPath and node == destination:
        return 1
    elif pathLength == maxPath or node == destination:
        return 0

    visited[node] = True

    sum = 0
    for k in neighbors[node]:
        if not visited[k]:
            sum += count(neighbors, visited, k, maxPath, pathLength + 1, destination)
    
    visited[node] = False
    return sum

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        count = 0
        visited = set()
        
        def dfs(i: int, j: int):
            nonlocal count
            nonlocal num_empty
            
            if grid[i][j] == -1 or (i, j) in visited:
                return
            # + 1 to account for starting position
            elif grid[i][j] == 2 and len(visited) == num_empty + 1:
                count += 1
                return
            else:
                visited.add((i, j))
                
                if i > 0:
                    dfs(i-1, j)
                if j > 0:
                    dfs(i, j-1)
                if i < len(grid) - 1:
                    dfs(i+1, j)
                if j < len(grid[0]) - 1:
                    dfs(i, j+1) 
                    
                visited.remove((i, j))
        
        # 1) Find starting position
        # 2) Count all empty squares
        start_i = start_j = None
        num_empty = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    start_i, start_j = i, j
                elif grid[i][j] == 0:
                    num_empty += 1
                    
        dfs(start_i, start_j)
        return count

class Solution:
    
    
    
    def find_square(self, grid, val):
        for i in range(0, len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == val:
                    return (i,j)
        return (-1,-1)
    
    def count_empty_squares(self, grid):
        empty_sq = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    empty_sq += 1
        return empty_sq
    
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        start_square = self.find_square(grid, 1)
        end_sq = self.find_square(grid, 2)
        empty_squares = self.count_empty_squares(grid) + 1
        
        
        def unique_paths_backtracking(grid, cur_sq, count):
            if count == empty_squares:
                if cur_sq == end_sq:
                    return 1
                return 0
            elif cur_sq == end_sq or \\
                not (0 <= cur_sq[0] < len(grid)) or \\
                not (0 <= cur_sq[1] < len(grid[0])) or \\
                grid[cur_sq[0]][cur_sq[1]] < 0:
                return 0

            grid[cur_sq[0]][cur_sq[1]] = -2
            u = unique_paths_backtracking(grid, (cur_sq[0]-1,cur_sq[1]), count+1)
            grid[cur_sq[0]][cur_sq[1]] = 0
            
            grid[cur_sq[0]][cur_sq[1]] = -2
            d = unique_paths_backtracking(grid, (cur_sq[0]+1,cur_sq[1]), count+1)
            grid[cur_sq[0]][cur_sq[1]] = 0
            
            grid[cur_sq[0]][cur_sq[1]] = -2
            l = unique_paths_backtracking(grid, (cur_sq[0],cur_sq[1]-1), count+1)
            grid[cur_sq[0]][cur_sq[1]] = 0
            
            grid[cur_sq[0]][cur_sq[1]] = -2
            r = unique_paths_backtracking(grid, (cur_sq[0],cur_sq[1]+1), count+1)
            grid[cur_sq[0]][cur_sq[1]] = 0
            
            return u + d + l + r
        
        
        return unique_paths_backtracking(grid, start_square, 0)
    
\"\"\"
1) Find starting square and ending square (write fn to do this)
2) Count number of empty squares
2) Fail conditions: 
    - we cannot travel any direction since we already visited them
    - we reach ending square but haven't stepped on every empty square
    - we reach an obstacle so terminate that path
3) Success:
    - squares explored == empty_squares and cur location is end_square idx
4) Increment a unique path counter every time we hit success condition

Runtime: O(4^(N*M))
Space: O(N*M)
\"\"\"

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        non_obstacles = 0
        start_row, start_col = 0, 0
        for row in range(0, rows):
            for col in range(0, cols):
                cell = grid[row][col]
                if cell >= 0:
                    non_obstacles += 1
                if cell == 1:
                    start_row, start_col = row, col
                    
        path_count = 0
        
        def backtrack(row, col, remain):
            nonlocal path_count
            
            if grid[row][col] == 2 and remain == 1:
                path_count += 1
                return
            
            temp = grid[row][col]
            grid[row][col] = -4
            remain -= 1
            
            for ro, co in [(0,1),(0,-1),(-1,0),(1,0)]:
                next_row, next_col = row + ro, col + co
                
                if not(0 <= next_row < rows and 0 <= next_col < cols):
                    continue
                if grid[next_row][next_col] < 0:
                    continue
                    
                backtrack(next_row, next_col, remain)
            
            grid[row][col] = temp
            
        backtrack(start_row, start_col, non_obstacles)
        
        return path_count


class Solution:
    '''
    - need to measure the the count of non-obstacles first O(n)
    - can use backtracking at each step
    - can go all directions, except if there is an obstacle or already visited
    - need to count how many available spots left, if we reach end, and spots left == 0, count as 1
    - O(3^n) time | O(n) space .. since we have n decisions at every step
    '''
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def traverse(row, col, spacesLeft):
            # end case
            if spacesLeft == 1 and grid[row][col] == 2:
                self.results += 1
                return
            
            # visit current
            temp = grid[row][col]
            grid[row][col] = '#'
            spacesLeft -= 1
            
            # visit next in all directions
            for rowOffset, colOffset in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nextRow, nextCol = row + rowOffset, col + colOffset
                # don't traverse if out of range
                if nextRow < 0 or nextRow == rows or nextCol < 0 or nextCol == cols:
                    continue
                # don't traverse if obstacle or visited
                if grid[nextRow][nextCol] == -1 or grid[nextRow][nextCol] == '#':
                    continue            
                traverse(nextRow, nextCol, spacesLeft)
            
            # backtrack
            grid[row][col] = temp
        
        rows, cols = len(grid), len(grid[0])
        spaces = 0
        # get data from grid first
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] >= 0:
                    spaces += 1
                if grid[row][col] == 1:
                    start = (row, col)
        
        self.results = 0
        traverse(start[0], start[1], spaces)
        return self.results

class Solution:
    '''
    - need to measure the the count of non-obstacles first O(n)
    - can use backtracking at each step
    - can go all directions, except if there is an obstacle or already visited
    - need to count how many available spots left, if we reach end, and spots left == 0, count as 1
    - O(3^n) time | O(n) space .. since we have n decisions at every step
    '''
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def traverse(row, col, spacesLeft):
            nonlocal results
            # end case
            if spacesLeft == 1 and grid[row][col] == 2:
                results += 1
                return
            
            # visit current
            temp = grid[row][col]
            grid[row][col] = '#'
            spacesLeft -= 1
            
            # visit next in all directions
            for rowOffset, colOffset in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nextRow, nextCol = row + rowOffset, col + colOffset
                # don't traverse if out of range
                if nextRow < 0 or nextRow == rows or nextCol < 0 or nextCol == cols:
                    continue
                # don't traverse if obstacle or visited
                if grid[nextRow][nextCol] == -1 or grid[nextRow][nextCol] == '#':
                    continue            
                traverse(nextRow, nextCol, spacesLeft)
            
            # backtrack
            grid[row][col] = temp
        
        rows, cols = len(grid), len(grid[0])
        spaces = 0
        # get data from grid first
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] >= 0:
                    spaces += 1
                if grid[row][col] == 1:
                    start = (row, col)
        
        results = 0
        traverse(start[0], start[1], spaces)
        return results

class Solution:
  def dfs(self, grid, r, c, i, j, count):
    if 0 <= i < r and 0 <= j < c and grid[i][j] != -1:
        if count == -1 and grid[i][j] == 2:
            self.res += 1
        val = grid[i][j]
        grid[i][j] = -1
        self.dfs(grid, r, c, i+1, j, count-1) 
        self.dfs(grid, r, c, i-1, j, count-1) 
        self.dfs(grid, r, c, i, j+1, count-1) 
        self.dfs(grid, r, c, i, j-1, count-1) 
        grid[i][j] = val   

  def uniquePathsIII(self, grid: List[List[int]]) -> int:
    \"\"\"
    1. Find start and end using a double for loop
    2. Use DFS to visit all available paths until we arrive at end then increment counter
    3. Use cache to return number of paths for lower trees
    4. Return the total amount of paths using the counter
    \"\"\"
    r, c, count = len(grid), len(grid[0]), 0
    for i in range(r):
        for j in range(c):
            count += grid[i][j] == 0
    self.res = 0 # treat it as a nonlocal variable
    for i in range(r):
        for j in range(c):
            if grid[i][j] == 1:
                self.dfs(grid, r, c, i, j, count)
    return self.res
                        

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def dfs(i,j,out,to_visit):
            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] == '#' or grid[i][j] == -1:
                return
            if grid[i][j] == 2 and to_visit == 0:
                out[0]+=1
            else:
                tmp = grid[i][j]
                grid[i][j] = '#'
                dfs(i,j+1,out,to_visit-1)
                dfs(i,j-1,out,to_visit-1)
                dfs(i+1,j,out,to_visit-1)
                dfs(i-1,j,out,to_visit-1)
                grid[i][j] = tmp
        
        res = [0]
        ori,orj = 0,0
        to_visit = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    ori,orj = i,j
                if grid[i][j] != -1:
                    to_visit += 1
        
        dfs(ori,orj,res,to_visit-1)
        
        return res[0]

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        start = end = None
        remain = 0
        for m in range(len(grid)):
            for n in range(len(grid[0])):
                if grid[m][n] == 1:
                    start = (m, n)
                elif grid[m][n] == 2:
                    end = (m, n)
                if grid[m][n] == 0:
                    remain += 1

        if start is None or end is None:
            return 0
        return self._helper(grid, start[0], start[1], end[0], end[1], remain + 1)

    def _helper(self, grid: List[List[int]], start_m: int, start_n: int, end_m: int, end_n: int, remain: int) -> int:
        if 0 <= start_m < len(grid) and 0 <= start_n < len(grid[0]) and grid[start_m][start_n] > -1:
            if remain < 0:
                return 0
            elif remain == 0 and start_m == end_m and start_n == end_n:
                return 1
            count = 0
            grid[start_m][start_n] = -2
            count += self._helper(grid, start_m + 1, start_n, end_m, end_n, remain - 1)
            count += self._helper(grid, start_m, start_n + 1, end_m, end_n, remain - 1)
            count += self._helper(grid, start_m - 1, start_n, end_m, end_n, remain - 1)
            count += self._helper(grid, start_m, start_n - 1, end_m, end_n, remain - 1)
            grid[start_m][start_n] = 0
            return count

        return 0

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        start = end = None
        cnt = ans = 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1: start = (i, j)
                elif grid[i][j] == 1: end = (i, j)
                if grid[i][j] != -1: cnt += 1
        def dfs(i, j, cnt):
            nonlocal m, n, ans
            if grid[i][j] == 2 and cnt == 1: 
                ans += 1 
                return
            val = grid[i][j]
            grid[i][j] = -1
            for x, y in map(lambda t: (t[0]+i, t[1]+j), [(-1, 0), (1, 0), (0, -1), (0, 1)]):
                if 0 <= x < m and 0 <= y < n and grid[x][y] != -1:
                    dfs(x, y, cnt-1)
            grid[i][j] = val
        dfs(*start, cnt)
        return ans 

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        # res = 0
        # m, n, empty = len(A), len(A[0]), 1
        # for i in range(m):
        #     for j in range(n):
        #         if A[i][j] == 1:
        #             x, y = (i, j)
        #         elif A[i][j] == 0:
        #             empty += 1
        # def dfs(x, y, empty):
        #     nonlocal res
        #     if not (0 <= x < m and 0 <= y < n and A[x][y] >= 0): return
        #     if A[x][y] == 2:
        #         res += empty == 0
        #         return
        #     A[x][y] = -2
        #     dfs(x + 1, y, empty - 1)
        #     dfs(x - 1, y, empty - 1)
        #     dfs(x, y + 1, empty - 1)
        #     dfs(x, y - 1, empty - 1)
        #     A[x][y] = 0
        # dfs(x, y, empty)
        # return res
        
        m, n = len(grid), len(grid[0])
        start = end = cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1: start = (i, j)
                elif grid[i][j] == 2: end = (i, j)
                if grid[i][j] != -1: cnt += 1 
        ans = 0
        def dfs(x, y, cnt):
            nonlocal ans, start, end
            if (x, y) == end and cnt == 1:
                ans += 1; return 
            val = grid[x][y]
            grid[x][y] = -1
            for i, j in map(lambda t: (t[0]+x, t[1]+y), [(-1, 0), (1, 0), (0, -1), (0, 1)]):
                if 0 <= i < m and 0 <= j < n and grid[i][j] != -1:
                    dfs(i, j, cnt-1)
            grid[x][y] = val
        dfs(*start, cnt)                    
        return ans

from collections import deque
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        r = c = -1
        
        count = 0
        node_count = 0
        ans = []
        for x in range(row):
            for y in range(col):
                if grid[x][y] >= 0:
                    node_count += 1
                  
                if grid[x][y] == 1:
                    r, c = x, y
                
        
        def get_paths(sr, sc, remain):
            
            left = sc - 1
            right = sc + 1
            up = sr - 1
            down = sr + 1
            
            nonlocal count
            
            if left >= 0 and grid[sr][left] == 0:
                #print(sr, left)
                grid[sr][left] = -4
                get_paths(sr, left, remain -1)
                grid[sr][left] = 0
                
            
            if right < col and grid[sr][right] == 0:
                #print(sr, right)
                grid[sr][right] = -4
                get_paths(sr, right, remain -1)
                grid[sr][right] = 0
            
            if up >= 0 and grid[up][sc] == 0:
                #print(up, sc)
                grid[up][sc] = -4
                get_paths(up, sc, remain -1)
                grid[up][sc] = 0
            
            if down < row and grid[down][sc] == 0:
                #print(down, sc)
                grid[down][sc] = -4
                get_paths(down, sc, remain -1)
                grid[down][sc] = 0
            
            if left >= 0 and grid[sr][left] == 2 and remain == 2:
                count += 1
            elif right < col and grid[sr][right] == 2 and remain == 2:
                count += 1
            elif up >= 0 and grid[up][sc] == 2 and remain == 2:
                count += 1
            elif down < row and grid[down][sc] == 2 and remain == 2:
                count += 1
            #print(remain)

        
        get_paths(r, c, node_count)
        return count


# General idea for the solution is as follows:
# 1) We traverse the whole array once initially, in doing so we find a) the location of the
#   start point, b) the location of the end point and c) the number of traversable square.
# 2) We then do a simple DFS traversal, like before. During this DFS traversal we can mark
#   previous nodes as visited in-place (replacing the original value on the backtrack).
#       - During the DFS traversal we count how many squares we have visited.
#       - We only increment the number of viable paths if we reach the end node after
#         visiting all the traversable nodes (i.e. count = 0, for example).

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        # First, traverse the array once, finding the start location and the number of -1
        # entries
        startIndex = None
        numTraversable = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # Find the start index
                if grid[i][j] == 1:
                    startIndex = [i, j]
                # Keep track of the number of obstacles
                if grid[i][j] != -1:
                    numTraversable += 1
        # Find the number of traversable squares (n * m - numObstables - 2)
        numTraversable -= 1 # -1 for start
        # Now call your DFS function from the starting node
        numPaths = self.visitedDFS(grid, startIndex, numTraversable)
        return numPaths

    def visitedDFS(self, grid, coord, count):
        numPaths = 0
        
        # First thing, check if the coorindates are out of bound or the node has been
        # visited/is an obstacle
        i, j = coord
        if (i < 0) or (j < 0) or (i >= len(grid)) or (j >= len(grid[0])) \\
        or (grid[i][j] < 0):
            return 0
        
        # Otherwise see if we're at the end coordinate
        if grid[i][j] == 2 and count == 0:
            return numPaths + 1
        
        # Otherwise mark this point as visited, or an obstacle
        saved = grid[i][j]
        grid[i][j] = -2
        
        # Do the DFS on the neighbours
        neighbours = [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]
        for neighbour in neighbours:
            numPaths += self.visitedDFS(grid, neighbour, count - 1)
            
        # Unmark the node
        grid[i][j] = saved
        
        return numPaths
    
    
    
    
        

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.ret = 0
        empty = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    sx = i
                    sy = j
                if grid[i][j] >= 0:
                    empty += 1
        
        def backtrack(grid, x, y, num_left):
            if x<0 or y<0 or x>=m or y>=n or grid[x][y] < 0:
                return
            if grid[x][y] == 2 and num_left == 0:
                self.ret += 1
                return
            neighs = [[0,1],[1,0],[0,-1],[-1,0]]
            for dx, dy in neighs:
                orig_value = grid[x][y]
                grid[x][y] = -1
                backtrack(grid, x+dx, y+dy, num_left-1)
                grid[x][y] = orig_value

        backtrack(grid, sx, sy, empty-1)
        return self.ret


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.ans, empty = 0, 0
        m, n = len(grid[0]), len(grid)
        def dfs(x, y, rest):
            if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] < 0:
                return
            
            if grid[x][y] == 2 and rest == 0:
                self.ans += 1
                return
            
            neibs = [[0,1],[0,-1],[1,0],[-1,0]]
            for dx, dy in neibs:
                tmp = grid[x][y]
                grid[x][y] = -2
                dfs(x+dx, y+dy, rest - 1)
                grid[x][y] = tmp
            
        for i,j in product(list(range(n)), list(range(m))):
            if grid[i][j] == 1:
                (sx, sy) = (i,j)
            empty += (grid[i][j] != -1)

        dfs(sx, sy, empty-1)
        return self.ans


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        # res = 0
        # m, n, empty = len(A), len(A[0]), 1
        # for i in range(m):
        #     for j in range(n):
        #         if A[i][j] == 1:
        #             x, y = (i, j)
        #         elif A[i][j] == 0:
        #             empty += 1
        # def dfs(x, y, empty):
        #     nonlocal res
        #     if not (0 <= x < m and 0 <= y < n and A[x][y] >= 0): return
        #     if A[x][y] == 2:
        #         res += empty == 0
        #         return
        #     A[x][y] = -2
        #     dfs(x + 1, y, empty - 1)
        #     dfs(x - 1, y, empty - 1)
        #     dfs(x, y + 1, empty - 1)
        #     dfs(x, y - 1, empty - 1)
        #     A[x][y] = 0
        # dfs(x, y, empty)
        # return res
        
        m, n = len(grid), len(grid[0])
        start = end = cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1: start = (i, j)
                elif grid[i][j] == 2: end = (i, j)
                if grid[i][j] != -1: cnt += 1 
        ans = 0
        def dfs(x, y, cnt):
            nonlocal ans, start, end
            if not (0 <= x < m and 0 <= y < n and grid[x][y] != -1): return
            if (x, y) == end and cnt == 1:
                ans += 1; return 
            val = grid[x][y]
            grid[x][y] = -1
            for i, j in map(lambda t: (t[0]+x, t[1]+y), [(-1, 0), (1, 0), (0, -1), (0, 1)]):
                dfs(i, j, cnt-1)
            grid[x][y] = val
        dfs(*start, cnt)                    
        return ans

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.ans, empty = 0, 0
        m, n = len(grid[0]), len(grid)
        def dfs(x, y, rest):
            if x < 0 or x >= n or y < 0 or y >= m or  grid[x][y] < 0: return
            if grid[x][y] == 2 and rest == 0:
                self.ans += 1
            
            neibs = [[0,1],[0,-1],[1,0],[-1,0]]
            for dx, dy in neibs:
                save = grid[x][y]
                grid[x][y] = -2
                dfs(x+dx, y+dy, rest - 1)
                grid[x][y] = save
            
        for i,j in product(list(range(n)), list(range(m))):
            if grid[i][j] == 1: (sx, sy) = (i,j)
            empty += (grid[i][j] != -1)

        dfs(sx, sy, empty-1)
        return self.ans


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        # step 1). initialize the conditions for backtracking
        #   i.e. initial state and final state
        non_obstacles = 0
        start_row, start_col = 0, 0
        for row in range(0, rows):
            for col in range(0, cols):
                cell = grid[row][col] 
                if  cell >= 0:
                    non_obstacles += 1
                if cell == 1:
                    start_row, start_col = row, col

        # count of paths as the final result
        path_count = 0

        # step 2). backtrack on the grid
        def backtrack(row, col, remain):
            # we need to modify this external variable
            nonlocal path_count
            print(grid)

            # base case for the termination of backtracking
            if grid[row][col] == 2 and remain == 1:
                # reach the destination
                path_count += 1
                return

            # mark the square as visited. case: 0, 1, 2 
            temp = grid[row][col] 
            grid[row][col] = -4
            remain -= 1   # we now have one less square to visit

            # explore the 4 potential directions around
            for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                next_row, next_col = row + ro, col + co

                if not (0 <= next_row < rows and 0 <= next_col < cols):
                    # invalid coordinate
                    continue
                if grid[next_row][next_col] < 0:
                    # either obstacle or visited square
                    continue

                backtrack(next_row, next_col, remain)

            # unmark the square after the visit
            grid[row][col] = temp

        backtrack(start_row, start_col, non_obstacles)

        return path_count

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        start_cell, end_cell = None, None
        empty_cells = {} # the set of neighbors' positions for each cell

        # collect empty cells
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] in [0, 1]:
                    empty_cells[(i, j)] = set()
                    if grid[i][j] == 1: start_cell = (i, j)
                elif grid[i][j] == 2: end_cell = (i, j)

        # collect their neighbors
        for x, y in empty_cells:
            for xch, ych in directions:
                neighbor = (x + xch, y + ych)
                if neighbor in empty_cells: empty_cells[(x, y)].add(neighbor)

        next_to_finish = set((end_cell[0] + xch, end_cell[1] + ych) for xch, ych in directions)
        visited=set([start_cell])
        def count_routes(cell=start_cell):
            left_to_visit = len(empty_cells) - len(visited)
            if not left_to_visit: return int(cell in next_to_finish)
            routes_to_end = 0
            for neighbor in (empty_cells[cell] - visited):
                visited.add(neighbor)
                routes_to_end += count_routes(neighbor)
                visited.remove(neighbor)
            return routes_to_end

        return count_routes()

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def dfs(r, c, n):
            if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == -1:
                return 0
            if grid[r][c] == 2:
                return n == 0
            grid[r][c] = -1
            paths = dfs(r + 1, c, n - 1) + dfs(r - 1, c, n - 1) + dfs(r, c + 1, n - 1) + dfs(r, c - 1, n - 1)
            grid[r][c] = 0
            return paths
        
        R = len(grid)
        C = len(grid[0])
        n = 1
        sr, sc = -1, -1
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 0:
                    n += 1
                elif grid[r][c] == 1:
                    sr, sc = r, c
        
        return dfs(sr, sc, n)


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.ans = 0
        m, n = len(grid), len(grid[0])
        candidates = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    si, sj = i, j
                elif grid[i][j] == 0 or grid[i][j] == 2:
                    candidates.add((i, j))
        
        def helper(i, j):
            if grid[i][j] == 2:
                if not candidates:
                    self.ans += 1
                return
            if grid[i][j] == -1:
                return
            if i < m - 1 and (i + 1, j) in candidates:
                candidates.remove((i+1, j))
                helper(i+1, j)
                candidates.add((i+1,j))
            if i > 0 and (i-1, j) in candidates:
                candidates.remove((i-1, j))
                helper(i-1, j)
                candidates.add((i-1,j))
                              
            if j < n - 1 and (i, j+1) in candidates:
                candidates.remove((i, j+1))
                helper(i, j+1)
                candidates.add((i,j+1))
            if j > 0 and (i, j-1) in candidates:
                candidates.remove((i, j-1))
                helper(i, j-1)
                candidates.add((i,j-1))
        
        helper(si, sj)
        return self.ans

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        
        self.ans, self.count = 0, 0
        def go(cur,seen):
            i,j = cur
            if grid[i][j] == 2:
                # print(self.count, len(seen))
                if len(seen) == self.count: self.ans+=1
                else: return
                
            for r,c, in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
                if 0<=r<len(grid) and 0<=c<len(grid[0]) and (r,c) not in seen and grid[r][c]!=-1:
                    seen.add((r,c))
                    go((r,c),seen)
                    seen.remove((r,c))
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] in [0,1,2]: self.count+=1
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    go((i,j), {(i,j)})
                    return self.ans
        
        
        
        return ans

class Solution:
    def uniquePathsIII(self, A: List[List[int]]) -> int:
        self.res = 0
        rows = len(A)
        cols = len(A[0])
        empty = 1
        for i in range(rows):
            for j in range(cols):
                if A[i][j] == 1: 
                    x,y = (i, j)
                elif A[i][j] == 2:
                    end = (i, j)
                elif A[i][j] == 0: 
                    empty += 1
        self.dfs(A,x,y, empty, end)
        return self.res
    def dfs(self, A, x, y, empty, end):
            if x < 0 or x >= len(A) or y < 0 or y >= len(A[0]) or A[x][y] < 0:
                return
            if (x, y) == end:
                self.res += empty == 0
                return
            A[x][y] = -2
            self.dfs(A,x + 1, y, empty - 1, end)
            self.dfs(A,x - 1, y, empty - 1, end)
            self.dfs(A,x, y + 1, empty - 1, end)
            self.dfs(A,x, y - 1, empty - 1, end)
            A[x][y] = 0

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def dfs(i,j,N):
            if N==-1 and grid[i][j]==2: return 1
            grid[i][j]=-1                    
            res = sum([dfs(row,col,N-1) for x,y in dirs for row,col in [(i+x,j+y)] if 0<=row<m and 0<=col<n and (N>0 and not grid[row][col] or N==0 and grid[row][col]==2)])
            grid[i][j]=0
            return res
            
        m,n = len(grid),len(grid[0])
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        N = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1: start=[i,j]
                elif not grid[i][j]: N+=1
        return dfs(start[0],start[1],N)

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        
        nr = len(grid)
        nc = len(grid[0])
        
        all_cells = 0
        start = (0, 0)
        res = 0
        
        direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] >= 0:
                    all_cells += 1
                if grid[r][c] == 1:
                    start = (r, c)
        
        def dfs(r, c, cell_nums):
            nonlocal res
            nonlocal direction
            nonlocal grid
            nonlocal nr
            nonlocal nc
            
            if grid[r][c] == 2 and cell_nums == 1:
                # reach the destination
                res += 1
                return
            
            temp = grid[r][c]
            grid[r][c] = -2
            cell_nums -= 1
            
            for d in direction:
                rr = r + d[0]
                cc = c + d[1]
                if 0 <= rr < nr and 0 <= cc < nc and grid[rr][cc] >= 0:
                    dfs(rr, cc, cell_nums)
                    
            grid[r][c] = temp
        dfs(*start, all_cells)
        return res