Minimum Changes To Make Valid Path

Hard
0/120
Average time to solve is 45m
profile
Contributed by
5 upvotes
Asked in company
Uber

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 3
DDD
RRL
UUU
2 2
UU
DD
Sample Output 1:
1
2
Explanation for Sample Output 1:
In test case 1, one of the paths is as follows:

(0,0) --> (1,0) --> (1,1) --> (1,2). Change the direction of (1,2) from ‘L’ to ‘D’. (1,2) -> (2,2).


In test case 2, one of the paths is as follows:

Change the direction of (0,0) cell to ‘R’.
(0,0) --> (0,1).

Change the direction of (0,1) cell from ‘U’ to ‘D’.
(0,1) --> (1,1).

Thus 2 changes are needed to reach (1,1) cell.
Sample Input 2:
2
1 1
D
2 2
RD
RD
Sample Output 2:
0
0
Explanation for Sample Output 2:
In test case 1, there is only one cell and so, we don't need any cell to change its direction. Thus, 0 will be the output.


In test case 2, No changes are required. Thus, 0 will be the output.
Hint

Use BFS to find a minimum number of changes to reach from. (0,0) cell to all other cells and it will lead us to get minimum answer.

Approaches (2)
BFS Approach

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:

 

  1. Create an auxiliary matrix ‘STEP’ of size ‘N’ X ‘M’ with default value infinite. Then initialize ‘STEP’[0][0] to 0.
  2. 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.
  3. 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.
  4. After breadth-first search return 'STEP['N' - 1]['M' - 1]'.
Time Complexity

O(N * M), Where ‘N’ and ‘M’ are number of rows and columns.

 

Since we will traverse all cells. Total number of cells are N * M. Hence time complexity is O(N * M).

Space Complexity

O(N * M), Where ‘N’ and ‘M’ are number of rows and columns.

 

Since we are creating an auxiliary matrix of size N * M. Hence space complexity is O(N * M).

Code Solution
(100% EXP penalty)
Minimum Changes To Make Valid Path
Full screen
Console