DIFFICULTY:
MEDIUM
PREREQUISITES:
GRAPH
PROBLEM:
The rescue team is initially at (X1, Y1) and the terrorists are hiding at (X2, Y2). You have to help the rescue team reach the terrorists in miminum number cost. However, there is a condition that the rescue team can take at most k steps to reach the terrorists such that |X2-X1| + |Y2-Y1| <= k. Only up, down, left and right direction movements are allowed. In the path, there is also a wall indicated by ‘X’ which the rescue team cannot cross. The rest of the village is represented in the grid as ‘0’. Output the minimum cost required to reach the terrorists. If not possible, output ‘-1’.
NOTE: You can jump the wall if k is greater than the distance to the wall
Value of k indicates the distance of one step. For example if k = 3, 3 steps in any direction (not necessary in a single direction) will be counted as one.
For example, one step to right and one step down will be counted as a single step if k=2
QUICK EXPLANATION:
The basic idea is to calculate the distance of each and every point till the destination. Doing so will help identify the required path length.
EXPLANATION:
After accepting all the inputs and the grid as well, replace the ‘X’ in the grid with 1 and keep remaining ‘0’ as it is. Initialize distances from all points to INT_MAX (a very big number) except the distance for (X1, Y1). Initialize it as 0.
To calculate the distances, check for the condition whether the point is directly reachable from the initial point using allowed moves and restrict the distance to at most ‘k’. Repeat this for all nodes in the grid. Output the value of distance at the starting node i.e. (X1, Y1).
Following code snippet can be considered for reference:
for(int i=x-k;i<=x+k;i++){
for(int j=y-k;j<=y+k;j++)
{
if(!a[i][j]&&dist[i][j]>dist[x][y]+1&&cd(x,y,i,j,k)&&check(i,j,n,m))
{
dist[i][j]=dist[x][y]+1;
q.push(make_pair(i,j));
}
}
}
TIME COMPLEXITY:
O(nm)
AUTHOR’S SOLUTION
You can find the solution here