 # Unique Paths III

Given a matrix of integers A of size N x M. There are 4 types of squares in it:

``````1. 1 represents the starting square.  There is exactly one starting square.
2. 2 represents the ending square.  There is exactly one ending square.
3. 0 represents empty squares we can walk over.
4. -1 represents obstacles that we cannot walk over.
``````

Find and return the number of 4-directional walks from the starting square to the ending square,
that walk over every non-obstacle square exactly once.

Note: Rows are numbered from top to bottom and columns are numbered from left to right.

Input Format

``````The first argument given is the integer matrix A.
``````

Output Format

``````Return the number of 4-directional walks from the starting square to the ending square,
that walk over every non-obstacle square exactly once.
``````

Constraints

``````2 <= N * M <= 20
-1 <= A[i] <= 2
``````

For Example

``````Input 1:
A = [   [1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 2, -1]   ]
Output 1:
2
Explanation 1: 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)

Input 2:
A = [   [0, 1]
[2, 0]    ]
Output 2:
0
``````
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details. 