316. Unique Paths III

HardBacktracking

You are given an `m x n` integer array `grid` where `grid[i][j]` could be: - `1` representing the **starting** square. There is exactly one starting square. - `2` representing the **ending** square. There is exactly one ending square. - `0` representing empty squares we can walk over. - `-1` representing 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

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

Output: 2

Explanation: Two distinct walks cover all 11 walkable squares exactly once and finish on the end square.

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 starting cell and one ending cell.

Run checks all cases above. Submit evaluates all test cases.