Minimum Direction Changes

Hard
0/120
Average time to solve is 50m
profile
Contributed by
11 upvotes
Asked in companies
AdobeAmazonOptum

Problem statement

Given a 2D grid having N Rows and M Columns. Each cell of the grid has a character among [ 'U', 'L', 'D', 'R' ] written on it, denoting Up, Left, Down, and Right respectively and indicating the direction in which it is permitted to move from that cell to its neighbor. Your task is to find the minimum number of cells whose direction value is required to be changed so that there exists a path from Top-Left to the Bottom-Right cell by following the directions written on the cells.

For example, 
Consider the 2 * 2 grid

sample inp 

Let's call the four cells in the grid as A,B,C,D. In this grid, it is allowed to move from Cell A to Cell B, Cell B to Cell D, Cell C to Cell D and Cell D to Cell C. There are two paths that start from A and ends at D:

1) A->C->D
To follow this path we need to change the value of cell A to “D” and do not need to change the value of cell C. Therefore, the total change for this path is 1.

2) A->B->D
To follow this path we need not to change any of the cell values. Therefore the total changes for this path is 0.

As we can see the minimum changes required to reach the bottom-right cell is Zero therefore the answer is 0 in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input format 
The first line of input contains an integer ‘T’ denoting the number of test cases.
Then the test cases follow.

The first line of each test case contains space-separated two numbers 'N' and 'M' denoting the number of rows and the number of columns in the grid respectively.

The next 'N' lines of each test case contain 'M' characters denoting the directions.
Output format: 
For each test case, print the minimum number of cells whose direction value is required to be changed so that there exists a path from Top-Left to the Bottom-Right cell.
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
Each cell of the grid will only have one of ['U', 'L', 'D', 'R'] character.

Time Limit: 1sec
Sample Input 1:
2
2 3
DRD
DRL
1 4
RRRR
Sample Output 1:
1
0
Explanation For Sample Input 1:
For the first test case:

sample inp

We can change the value of the leftmost cell of the bottom row from 'D' to 'R' or we can change the value of the starting cell from 'D' to 'R' to get a path from the Top-Left to 
Bottom-Right cell. Therefore, the minimum direction change required in this case is 1.

For the second test case:
All the cells only allow moving to the right direction. So a path from leftmost to the rightmost cell already exists in this case. Therefore, the answer is 0 in this case.
Sample Input 2:
2 
3 3
DRR
DRR
DRR
1 1
L
Sample Output 2:
1
0
Hint

Try to build a Directed Weighted Graph for the grid.

Approaches (1)
Graph based Solution

As we know if we change the direction of a cell to any other neighbour to move from cell to its neighbour, then it will cost 1 change, and if we follow the given cell direction then it will cost 0 as we follow the same direction which is given. So now we can see that we have 4 choices at each cell to move to its neighbour by cost 1 or 0, and we can also say that if we make this choice as an edge i.e at any cell there is a path to move to its neighbour either with cost 1 or 0.

 

So we can build a Directed Weighted Graph for the grid in which the edge will have weight 0 or 1. Now, the problem is to find out the shortest distance between Top-Left and Bottom-Right cell.

 

The idea to build the graph is elaborated below:

 

  • Initialize a matrix adj[N][M] of vectors storing the adjacency list of each cell.
  • For each cell of the grid:
    • Add a directed edge between the cell and its neighbour already given in the cell with a weight of 0.
    • Add a directed edge between the cell and other neighbours with a weight of 1.

 

See the below grid for a better understanding:

For the given 3 * 3 grid. The edges shown are the ones having 0 weight, and It will need 1 direction change to move from a cell to any other neighbour cell using an edge that is not among the above-shown edges.

 

After building the adjacency list of the grid, we can apply any of the Single Source Shortest Path Graph Algorithms to find out the shortest distance between the Top-Left cell and the Bottom-Right cell. 

 

We will be using Dijkstra's Algorithm for our implementation to find the shortest distance.

Time Complexity

O(N * M * log(N * M)), where ‘N’ is the number of rows in the grid and 'M' is the number of columns in the grid.

 

In the worst case, Dijkstra's Algorithm has Time complexity of O(E * log(V)). In our implementation, E is 4 * N * M and V is N * M. So the overall time complexity will be O(N * M * log(N * M)).

Space Complexity

O(N * M), where ‘N’ is the number of rows in the grid and 'M' is the number of columns in the grid.

 

In the worst case, we need to store only the adjacency lists and the Shortest Distance Matrix. The number of elements in both of them is N * M. So the overall space complexity is O(N * M).

Code Solution
(100% EXP penalty)
Minimum Direction Changes
Full screen
Console