Last Updated: 17 Sep, 2021
Go For Gold
Hard
Asked in company
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.
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
Approaches
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.