Last Updated: 22 Mar, 2021
Minimum Changes To Make Valid Path
Hard
Asked in company
Given a matrix of size ‘N’ x ’M’. Each cell in a grid has a character denoting the next cell that can be visited from the current cell. If 'MATRIX'[i][j] is equal to:
‘U’:- then from (i,j) you can visit (i - 1, j) only if i - 1 >= 0.
‘D’:- then from (i,j) you can visit (i + 1, j) only if i + 1 < n.
‘R’:- then from (i,j) you can visit (i, j + 1) only if j + 1 < m.
‘L’:- then from (i,j) you can visit (i, j - 1) only if j - 1 >= 0.
You can change the direction of each cell at most one time.
You need to determine a minimum number of changes you need to make to reach from the cell (0,0) to the cell('N' - 1, 'M' - 1).
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of the test case contains 2 integers ‘N’ and ‘M’ denoting the length and width of the matrix.
The next ‘N’ lines contain ‘M’ characters each denoting the direction of the cell of the matrix.
Output Format:
For each test case, print a single integer denoting a minimum number of cell’s direction need to change to reach from (0,0) to ('N' - 1, 'M' - 1).
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1<= T <=10
1<= N, M <=100
MATRIX[i][j] = {‘D’,’R’,’U’,’L’}.
Time limit: 1 sec
Approaches
Explanation:-The main idea is to use a breadth-first search to find minimum changes to reach from the cell (0,0) to all other cells. The cell will be added in the queue if the steps of the current cell is less than the given cell.
The steps are as follows:
- Create an auxiliary matrix ‘STEP’ of size ‘N’ X ‘M’ with default value infinite. Then initialize ‘STEP’[0][0] to 0.
- Start breadth-first from (0,0) cell. Now traverse the director present at the current cell. If it does not lie outside the matrix then check the steps of the current cell is less than the steps of the cell then update the steps of the cell with the current cell. Add the cell in the queue.
- Now traverse all the remaining directions. First, check if the cell lies outside the matrix then move to the next direction. Else check if steps of the cell are less than steps of current cell + 1(Since we are changing the direction. Hence we are adding 1). then update the steps of the cell with the current cell + 1 and add the cell in the queue.
- After breadth-first search return 'STEP['N' - 1]['M' - 1]'.
Explanation:-The main idea is to use a (0-1) breadth-first search and dequeue to find the minimum distance. We will convert this matrix into a weighted undirected graph of weights 0 and 1.So our problem becomes to find the shortest path from the source (0,0) to the target (m-1,n-1).
The steps are as follows:
- Create a hashmap and dequeue ‘PQ’ and insert (0,0)(source) and 0(shortest path from source to source is 0) in the front of ‘PQ’.
- Now start the bfs from the source cell.If the current vertex is visited then move on. Else mark it visited. If it is equal to the target vertex then return the path sum.
- Now traverse the direction present at the current cell. If it does not lie outside the matrix and it is not visited then insert it in front of ‘PQ’ and with path sum equal to path sum of the current cell.
- Now traverse all the remaining directions. First, check if the cell does not lie outside the matrix and it is not visited. Now insert the cell into the end of ‘PQ’ with path sum equal to path sum of current cell + 1(since we are changing the direction of the current cell).