# 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

class Solution(object):
    def uniquePathsIII(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        self.res = 0

        for i in xrange(len(grid)):
            for j in xrange(len(grid[i])):
                if grid[i][j] == 1:
                    self.dfs(grid, i, j)

        return self.res

    def dfs(self, grid, x, y):
        if grid[x][y] == 2 and self.isValid(grid):
            self.res += 1
            return

        for c, r in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            nX, nY = x + c, y + r
            if 0 <= nX < len(grid) and 0 <= nY < len(grid[0]) and grid[nX][nY] in [0, 2]:
                if grid[nX][nY] == 0:
                    grid[nX][nY] = 3
                    self.dfs(grid, nX, nY)
                    grid[nX][nY] = 0  # backtrack

                elif self.isValid(grid):  # we reach 2 and we walk-through all 0 square
                    self.dfs(grid, nX, nY)

    def isValid(self, grid):
        for i in xrange(len(grid)):
            for j in xrange(len(grid[i])):
                if not grid[i][j]:
                    return False
        return True


if __name__ == '__main__':
    print Solution().uniquePathsIII([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]])
    print Solution().uniquePathsIII([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2]])
    print Solution().uniquePathsIII([[0, 1], [2, 0]])
