Go For Gold

Hard
0/120
profile
Contributed by
6 upvotes
Asked in company
Adobe

Problem statement

Ninja is on a hunt to collect all the gold from the city of Ninjago and reach his home as soon as possible.

You are given a matrix ‘Arr’ consisting of ‘M’ rows and ‘N’ columns denoting houses in the city of Ninjago.

Arr[i][j] = 0 denotes that the house is empty
Arr[i][j] = 1 denotes that the house has exactly one gold bar
Arr[i][j] = 2 denotes that the house is secured by the guards

Ninja starts from the position (0, 0) and wants to reach the position (X, Y) after collecting all the gold from the city, he can move to any adjacent house that is not secured by the guards but he is not allowed to go outside the city. In other words, he can move one unit up, down, left or right in a single move, but he is neither allowed to move to a house that is secured by guards nor can he leave the matrix.

Find the minimum number of steps required to accomplish the task of collecting all the tasks and reaching his final destination. If it is not possible to complete the task, then return ‘-1’

Note : 
Ninja may visit a house multiple times, but he will be able to collect the gold bar only once from that house.
For Example : 
If ‘Arr’ consists of 4 rows and 5 columns and is denoted as:
0 1 1 2 0
2 2 1 1 2
0 0 1 2 0
0 1 1 0 0
And ninja’s home is located at (2, 1).


The minimum number of moves required to complete the task is equal to 9, because:
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 3) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 1) -> (2, 1) is the most optimal route to complete the task.
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 integers ‘M’ and ‘N’ denoting the number of rows and columns.

The following M rows each contain N integers denoting the status of each house.

The last line of each test case contains two integers ‘X’ and ‘Y’ denoting the x-coordinate and y-coordinate of Ninja’s house (his final destination).
Output Format : 
For each test case, print a single integer denoting the minimum number of steps required.

Output for each test case will be printed in 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      
1 <= M, N <= 20
Arr[i][j] = {0, 1, 2}
1 <= Number of houses with gold <= 7
0 <= X < M ,  0 <= Y < N

Time limit: 1 sec
Sample Input 1 :
2
4 5
0 1 1 2 0
2 2 1 1 2
0 0 1 2 0
0 1 1 0 0
2 1
1 3
0 0 1
0 1
Sample Output 1 :
9
3
Explanation For Sample Input 1 :
For test case 1 : 
We will return 9, because:
(0,0) -> (0,1) -> (0,2) -> (1,2) -> (1,3) -> (1,2) -> (2,2) -> (3,2) -> (3,1) -> (2,1) is the most optimal route to complete the task.


For test case 2 : 
We will return 3, because:
(0,0) -> (0,1) -> (0,2) -> (0,1) is the most optimal route to complete the task.
Sample Input 2 :
2
3 3
0 2 0
2 0 0
0 0 0
1 1
3 3 
0 0 0
0 0 0
0 0 0
2 2
Sample Output 2 :
-1
4
Hint

All we are concerned with is that we have to collect all the gold, once we have thought of how to tackle this, then we have to think of a way to collect all the gold in the most optimal way. As our intuition is revolving around gold, can we create a bitmask for these houses? How will this help us? 

Approaches (1)
BFS + Bitmasking

There can be at max eight houses that can contain gold in them. We can easily number these houses starting from 0, now we can use “MASK” as our bitmask. We will initially set all the bits equal to 0 in “MASK”, now while applying breadth-first search if we visit the ith house containing gold then we will set the ith bit in “MASK” as 1. 

We will store the minimum distance  to reach the position (x,y) in distance[ { x, y, MASK } ], and we will finally return the value of distance[ { X, Y, (111...1)2 } ].


 

The steps are as follows :

  • Initialize a map “mp” to store the the house number number for each of the gold-houses.
  • Initialize a variable “num”  to number the gold-houses.
  • Traverse the input ‘Arr’ to find all the houses containing gold.
  • Initialize a variable “target” equal to 2num.
  • Initialize a bit-mask “mask” and set all the values to -1, where mask[i][j][k] represents the minimum steps to reach (i,j) given that we have already covered the gold-houses corresponding to set bits in the binary representation of 'k'.
  • Initialize a variable “steps” equal to 0, also initialize an array to simulate the moves easily and also initialize a bfs-queue.
  • Check if the starting position (0, 0) is itself a gold-house and start the bfs according to that.
  • For the next position, check if it’s valid. Then check if it is a gold-house or not, if it is a gold-house check for the masked bit. If it is not gold house then check if the current masked value is already visited or not, If not then insert it into the bfs-queue.
  • Stop the breadth-first search if you reach (X, Y) and the mask is equal to target-1, and return the value of “steps”.
  • In case you are not able to reach the final position after collecting all the gold then return -1.
Time Complexity

O( M * N * ( 2 ^ G )  ), where M denotes the number of rows, N denotes the number of columns and G denotes the number of houses contain gold

 

In the worst-case, we might have to explore all the positions of the order ~N*M with all the possible mask values that can be of the order ~2^G.

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

Space Complexity

O( M * N * ( 2 ^ G )  ), where M denotes the number of rows, N denotes the number of columns and G denotes the number of houses contain gold

 

We create a 3-D array of dimensions N by M by 2^G to store the minimum steps required to reach (i, j) when we have already collected gold from some houses stored as a mask. 

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

Code Solution
(100% EXP penalty)
Go For Gold
Full screen
Console