Minimum Changes To Make Valid Path

Posted: 22 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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
Approach 1

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]'.
Try Problem