Unique Paths III

You are given an m x n integer array grid where:

• 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.

Examples

Example 1

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

Output: 2

Explanation: There are two paths that visit every non-obstacle cell exactly once: right→right→right→down→down and right→right→down→down→right (adapting direction as needed).

Example 2

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]

Output: 4

Explanation: There are four valid Hamiltonian paths from the start to the end covering all empty cells.

Example 3

Input: grid = [[0,1],[2,0]]

Output: 0

Explanation: No path from start to end can visit all 4 non-obstacle cells exactly once.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• 1 <= m * n <= 20
• -1 <= grid[i][j] <= 2
• There is exactly one 1 and one 2 in grid