Unique Paths III

Hard
0/120
profile
Contributed by
6 upvotes
Asked in companies
AmazonMicrosoft

Problem statement

Robot is given a task to clean a room. The room can be visualized as a matrix ‘ARR’ containing ‘N’ rows and ‘M’ columns. The cells of the room are denoted as:

1) Cells with a value of 0 indicate empty space in the room.
2) Cells with a value of -1 indicate an obstacle in the room.
3) Cell with a value of 1 indicates the starting position of the robot.
4) Cell with a value of 2 indicates the ending position of the robot.

In each move, the robot is only allowed to move to one of the four adjacent cells if it exists and is not occupied by an obstacle. Robot has to clean this room entirely. To complete this task his path must start from his starting cell and should visit all the empty cells (denoted by value 0) exactly once, and he should finally arrive at the ending cell. You have to find the number of all possible paths using which the robot can clean the room.

Note that the cells corresponding to the starting and ending position of the robot are never occupied by an obstacle. And starting and ending positions will always be in different cells.

For Example : 
If ‘N’ = 3, ‘M’ = 3 and ‘ARR’ = [ [1, 0, 0], [0, 0, 0], [0, 0, 2] ]

Then the room is represented as:


The 2 unique paths are marked in the image above.
The first path is: (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2).

The second path is: (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (1, 1) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the number of rows and columns respectively.

The next N lines each contain M space-separated integers ‘ARR’, denoting each cell of the room.
Output Format : 
For each test case, find the number of unique paths using which the robot can clean the room.

Output for each test case will be printed on a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
2 ≤ N, M ≤ 5
ARR[i] = { -1, 0, 1, 2 }
The robot will always have valid starting and ending positions.

Time limit: 1 sec
Sample Input 1 :
2
3 3
1 0 0
0 0 0
0 0 2
3 3
1 0 0
0 -1 0
0 0 2
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
For test case 1 :
We will print 2 because there are two unique paths possible:
The first path is: (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2).
The second path is: (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (1, 1) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2).

For test case 2 : 
We will print 0 because:
There exists no path in which we can clean all the empty cells while visiting them exactly once.
Sample Input 2 :
2
2 2
1 2
0 0
2 2
1 0
0 2
Sample Output 2 :
1
0
Hint

Backtrack to explore all possible paths.

Approaches (1)
Backtracking

It’s easy to figure out that we can solve this problem using a standard backtracking practice. We explore the path till the end, while exploring if we ever find any discrepancy on the condition to be satisfied then we revert back to the last change to explore other options of our last stage.

 

To solve this question we can start from the starting cell of the robot, we can use the input matrix itself to store the cells we have already visited by exploring the current route. We must also store a counter to keep track of the number of cells we have currently visited by exploring the current path. If we are currently at some (i, j) cell then we can try visiting all its neighbouring cells in a depth-first search matter. If at a later stage we get stuck at a place in which we don’t have any adjacent cells that are unvisited then we can simply revert back to the previous cell we came from to explore other routes, note that standard backtracking also involves marking the cell as unvisited when we revert back to the previous cell.

 

Each time we reach the final cell, we can check if the count of cells in our path is equal to the desired count then we can increment the value of our final answer to be returned.

 

The steps are as follows :

  1. Declare and initialize a global array 'moves'. This will help us to visit the adjacent cells easily while implementing.
  2. Declare two variables to store the indices of the starting cell.
  3. Also, declare a variable ‘left’ to store the total cells to be visited in each path.
  4. Iterate through all the cells of the matrix, and update the value of ‘left’, also find the starting cell.
  5. Declare a variable ‘paths’, this will store the count of all the unique paths.
  6. Make an initial call to the recursive function passing the indices corresponding to the starting cell as the current indices.
  7. Inside the recursive function:
    • Decrement the value of ‘left’ as we have visited the current cell.
    • Visit the adjacent cells, take care of the out of bounds condition. Use ‘moves’ array for simpler implementation:
      • If the adjacent cell is the ending cell, then don’t make any other further recursive calls, and also check if the total remaining cells to be visited is equal to 1 then it signifies we have visited all the empty cells and now just need to visit the ending cell. Increment the value of ‘paths’ for this case.
      • If the adjacent cell is not an ending cell and if also unvisited till now, then mark it as visited and make a recursive call. Once the recursive call ends, using standard backtracking logic, mark this cell as unvisited.
  8. Finally, return ‘paths’, as it stores the count of unique paths.
Time Complexity

O( 3 ^ ( N * M ) ), where N and M denote the number of rows and columns.

 

Intuitively one might figure out for each position we need to explore all the four directions, so in general, we might end up making four recursive calls to visit the adjacent cells, this, in turn, gives a time complexity of ~4^(N*M), but on careful observation, it's easy to figure out that at max we will require to explore three recursive calls, as we won’t be going to the adjacent cell we just came from.

Hence the time complexity is O( 3^(N*M)  ).

Space Complexity

O( N * M ), where N and M denote the number of rows and columns.

 

In the worst-case, there can be ~N*M recursive calls in the stack frame of the memory.

Hence the space complexity is O( N*M ).

Code Solution
(100% EXP penalty)
Unique Paths III
Full screen
Console