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.
Start solving Unique Paths III on Interview Code Editor
Sign Up
to access hints and editorial solutions for Unique Paths III

Discussion


Loading...
Click here to start solving coding interview questions