Minimum cost to reach the last cell of a grid with directions
Given a 2D matrix grid[][] of size M X N, where each cell of the grid has a character denoting the next cell we should visit we are at the current cell. The character at any cell can be:
- βRβ which means go to the cell to the right. (i.e from grid[i][j] to grid[i][j + 1])
- βLβ which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j β 1])
- βDβ which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
- βUβ which means go to the upper cell. (i.e go from grid[i][j] to grid[i β 1][j])
At any cell (i, j) we can either move in the direction denoted by character grid[i][j] with a cost of 0 or we can move in some other direction with a cost of 1. Starting from the cell (0, 0), the task is to reach cell (M-1, N-1) with minimum cost. The path does not have to be the shortest.
Note: The character may point to the outside of the grid as well.
Examples:
Input: N = 4, M = 4, grid[][]= {{βRβ, βRβ, βRβ, βRβ}, {βLβ, βLβ, βLβ, βLβ}, {βRβ, βRβ, βRβ, βRβ}, {βLβ, βLβ, βLβ, βLβ}}
Output: 3
Explanation: The path from (0, 0) to (3, 3) is:
- (0, 0) -> (0, 1) -> (0, 2) -> (0, 3), cost = 0
- (0, 3) -> (1, 3), cost = 1
- (1, 3) -> (1, 2) -> (1, 1) -> (1, 0), cost = 0
- (1, 0) -> (2, 0), cost = 1
- (2, 0) -> (2, 1) β> (2, 2) β> (2, 3), cost = 0
- (2, 3) -> (3, 3), cost = 1
The total cost = 0 + 1 + 0 + 1 + 0 + 1 = 3.
Input: N = 3, M = 3, grid = {{βRβ, βRβ, βDβ}, {βDβ, βLβ, βLβ}, {βRβ, βRβ, βUβ}}
Output: 0
Explanation: The path from (0, 0) to (2, 2) is:
- (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2), cost = 0
The total cost = 0.
Approach: To solve the problem, follow the below idea:
The problem can be solved using 0-1 BFS by considering the grid as a graph where edge weights are limited to 0 and 1 only. If we move in the same direction as denoted by the current cell, then the edge cost will be 0 otherwise if we move in any other direction, then the edge cost will be 1. Now, we can run a 0-1 BFS using a deque to find the minimum cost from cell (0, 0) to cell (M β 1, N β 1).
Step-by-step algorithm:
- Maintain a deque of pairs, say dq to store the row and column of the cells.
- Also maintain a cost[][] array, such that cost[i][j] stores the minimum cost to reach cell (i, j) starting from (0, 0).
- Push the cell (0, 0) to the dq.
- Iterate till dq is not empty:
- Pop the front element (r, c).
- For all the neighboring cells, push the cell to the front of dq if the neighboring cell is in the same direction as denoted by grid[r], otherwise push the cell to the back of dq.
- Also, the cell will only be pushed if the cell has not been visited yet.
- We can keep track of the visited cells using the cost[][] array.
- Finally, return the value stored at cost[M β 1][N β 1].
Below is the implementation of the algorithm:
C++
#include <iostream> #include <vector> #include <deque> using namespace std; // Method to check whether a cell is in the grid or not bool isValid( int r, int c, int M, int N) { return r >= 0 && c >= 0 && r < M && c < N; } // Method to find the minimum cost to reach cell (M-1, N-1) int minCost(vector<vector< char >>& grid) { // 0-1 BFS deque<pair< int , int >> dq; int M = grid.size(), N = grid[0].size(); // vector to store the minimum cost to reach a // particular cell vector<vector< int >> cost(M, vector< int >(N, 1e9)); cost[0][0] = 0; dq.push_back({0, 0}); int dr[] = {0, 0, -1, 1}; int dc[] = {1, -1, 0, 0}; while (!dq.empty()) { int r = dq.front().first; int c = dq.front().second; dq.pop_front(); for ( int i = 0; i < 4; i++) { int new_r = r + dr[i]; int new_c = c + dc[i]; if (isValid(new_r, new_c, M, N)) { int new_d = cost[r]; bool directionChange = false ; // If the next cell is in a different // direction if ((grid[r] != 'R' && dr[i] == 0 && dc[i] == 1) || (grid[r] != 'L' && dr[i] == 0 && dc[i] == -1) || (grid[r] != 'D' && dr[i] == 1 && dc[i] == 0) || (grid[r] != 'U' && dr[i] == -1 && dc[i] == 0)) { new_d += 1; directionChange = true ; } // If the cell is unvisited if (cost[new_r][new_c] > new_d) { cost[new_r][new_c] = new_d; // If the next cell is in the same // direction as written in grid[r] if (directionChange) { dq.push_back({new_r, new_c}); } // If the next cell is in a different // direction as written in grid[r] else { dq.push_front({new_r, new_c}); } } } } } return cost[M - 1][N - 1]; } int main() { vector<vector< char >> grid = {{ 'R' , 'R' , 'R' , 'R' }, { 'L' , 'L' , 'L' , 'L' }, { 'R' , 'R' , 'R' , 'R' }, { 'L' , 'L' , 'L' , 'L' }}; cout << minCost(grid) << "\n" ; return 0; } |
Java
import java.util.ArrayDeque; import java.util.Deque; public class Main { // Method to check whether a cell is in the grid or not static boolean isValid( int r, int c, int M, int N) { return r >= 0 && c >= 0 && r < M && c < N; } // Method to find the minimum cost to reach cell (M-1, N-1) static int minCost( char [][] grid) { // 0-1 BFS Deque< int []> dq = new ArrayDeque<>(); int M = grid.length, N = grid[ 0 ].length; // Array to store the minimum cost to reach a // particular cell int [][] cost = new int [M][N]; for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) { cost[i][j] = Integer.MAX_VALUE; } } cost[ 0 ][ 0 ] = 0 ; dq.addLast( new int []{ 0 , 0 }); int [] dr = { 0 , 0 , - 1 , 1 }; int [] dc = { 1 , - 1 , 0 , 0 }; while (!dq.isEmpty()) { int [] current = dq.pollFirst(); int r = current[ 0 ]; int c = current[ 1 ]; for ( int i = 0 ; i < 4 ; i++) { int new_r = r + dr[i]; int new_c = c + dc[i]; if (isValid(new_r, new_c, M, N)) { int new_d = cost[r]; boolean directionChange = false ; // If the next cell is in a different direction if ((grid[r] != 'R' && dr[i] == 0 && dc[i] == 1 ) || (grid[r] != 'L' && dr[i] == 0 && dc[i] == - 1 ) || (grid[r] != 'D' && dr[i] == 1 && dc[i] == 0 ) || (grid[r] != 'U' && dr[i] == - 1 && dc[i] == 0 )) { new_d += 1 ; directionChange = true ; } // If the cell is unvisited if (cost[new_r][new_c] > new_d) { cost[new_r][new_c] = new_d; // If the next cell is in the same direction // as written in grid[r] if (directionChange) { dq.addLast( new int []{new_r, new_c}); } // If the next cell is in a different // direction as written in grid[r] else { dq.addFirst( new int []{new_r, new_c}); } } } } } return cost[M - 1 ][N - 1 ]; } public static void main(String[] args) { char [][] grid = { { 'R' , 'R' , 'R' , 'R' }, { 'L' , 'L' , 'L' , 'L' }, { 'R' , 'R' , 'R' , 'R' }, { 'L' , 'L' , 'L' , 'L' } }; System.out.println(minCost(grid)); } } // This code is contributed by rambabuguphka |
C#
using System; using System.Collections.Generic; class Program { // Method to check whether a cell is in the grid or not static bool IsValid( int r, int c, int M, int N) { return r >= 0 && c >= 0 && r < M && c < N; } // Method to find the minimum cost to reach cell (M-1, N-1) static int MinCost( char [][] grid) { // 0-1 BFS var dq = new Queue<Tuple< int , int >>(); int M = grid.Length, N = grid[0].Length; // vector to store the minimum cost to reach a // particular cell var cost = new int [M][]; for ( int i = 0; i < M; i++) { cost[i] = new int [N]; for ( int j = 0; j < N; j++) { cost[i][j] = int .MaxValue; } } cost[0][0] = 0; dq.Enqueue( new Tuple< int , int >(0, 0)); int [] dr = { 0, 0, -1, 1 }; int [] dc = { 1, -1, 0, 0 }; while (dq.Count > 0) { var front = dq.Dequeue(); int r = front.Item1; int c = front.Item2; for ( int i = 0; i < 4; i++) { int new_r = r + dr[i]; int new_c = c + dc[i]; if (IsValid(new_r, new_c, M, N)) { int new_d = cost[r]; bool directionChange = false ; // If the next cell is in a different // direction if ((grid[r] != 'R' && dr[i] == 0 && dc[i] == 1) || (grid[r] != 'L' && dr[i] == 0 && dc[i] == -1) || (grid[r] != 'D' && dr[i] == 1 && dc[i] == 0) || (grid[r] != 'U' && dr[i] == -1 && dc[i] == 0)) { new_d += 1; directionChange = true ; } // If the cell is unvisited if (cost[new_r][new_c] > new_d) { cost[new_r][new_c] = new_d; // If the next cell is in the same // direction as written in grid[r] if (directionChange) { dq.Enqueue( new Tuple< int , int >(new_r, new_c)); } // If the next cell is in a different // direction as written in grid[r] else { dq.Enqueue( new Tuple< int , int >(new_r, new_c)); } } } } } return cost[M - 1][N - 1]; } static void Main() { char [][] grid = { new char [] { 'R' , 'R' , 'R' , 'R' }, new char [] { 'L' , 'L' , 'L' , 'L' }, new char [] { 'R' , 'R' , 'R' , 'R' }, new char [] { 'L' , 'L' , 'L' , 'L' } }; Console.WriteLine(MinCost(grid)); } } |
Javascript
// Method to check whether a cell is in the grid or not function isValid(r, c, M, N) { return r >= 0 && c >= 0 && r < M && c < N; } // Method to find the minimum cost to reach cell (M-1, N-1) function minCost(grid) { // 0-1 BFS const dq = []; const M = grid.length; const N = grid[0].length; // matrix to store the minimum cost to reach a particular cell const cost = Array.from({ length: M }, () => Array(N).fill(1e9)); cost[0][0] = 0; dq.push([0, 0]); const dr = [0, 0, -1, 1]; const dc = [1, -1, 0, 0]; while (dq.length > 0) { const [r, c] = dq.shift(); for (let i = 0; i < 4; i++) { const new_r = r + dr[i]; const new_c = c + dc[i]; if (isValid(new_r, new_c, M, N)) { let new_d = cost[r]; let directionChange = false ; // If the next cell is in a different direction if ( (grid[r] !== 'R' && dr[i] === 0 && dc[i] === 1) || (grid[r] !== 'L' && dr[i] === 0 && dc[i] === -1) || (grid[r] !== 'D' && dr[i] === 1 && dc[i] === 0) || (grid[r] !== 'U' && dr[i] === -1 && dc[i] === 0) ) { new_d += 1; directionChange = true ; } // If the cell is unvisited if (cost[new_r][new_c] > new_d) { cost[new_r][new_c] = new_d; // If the next cell is in the same direction if (directionChange) { dq.push([new_r, new_c]); } else { dq.unshift([new_r, new_c]); } } } } } return cost[M - 1][N - 1]; } // Example usage const grid = [ [ 'R' , 'R' , 'R' , 'R' ], [ 'L' , 'L' , 'L' , 'L' ], [ 'R' , 'R' , 'R' , 'R' ], [ 'L' , 'L' , 'L' , 'L' ] ]; console.log(minCost(grid)); |
Python3
from collections import deque # Method to check whether a cell is in the grid or not def is_valid(r, c, M, N): return 0 < = r < M and 0 < = c < N # Method to find the minimum cost to reach cell (M-1, N-1) def min_cost(grid): # 0-1 BFS dq = deque() M, N = len (grid), len (grid[ 0 ]) # list to store the minimum cost to reach a particular cell cost = [[ 1e9 ] * N for _ in range (M)] cost[ 0 ][ 0 ] = 0 dq.append(( 0 , 0 )) dr = [ 0 , 0 , - 1 , 1 ] dc = [ 1 , - 1 , 0 , 0 ] while dq: r, c = dq.popleft() for i in range ( 4 ): new_r = r + dr[i] new_c = c + dc[i] if is_valid(new_r, new_c, M, N): new_d = cost[r] direction_change = False # If the next cell is in a different direction if ((grid[r] ! = 'R' and dr[i] = = 0 and dc[i] = = 1 ) or (grid[r] ! = 'L' and dr[i] = = 0 and dc[i] = = - 1 ) or (grid[r] ! = 'D' and dr[i] = = 1 and dc[i] = = 0 ) or (grid[r] ! = 'U' and dr[i] = = - 1 and dc[i] = = 0 )): new_d + = 1 direction_change = True # If the cell is unvisited if cost[new_r][new_c] > new_d: cost[new_r][new_c] = new_d # If the next cell is in the same direction as written in grid[r] if direction_change: dq.append((new_r, new_c)) # If the next cell is in a different direction as written in grid[r] else : dq.appendleft((new_r, new_c)) return cost[M - 1 ][N - 1 ] # Test the function grid = [[ 'R' , 'R' , 'R' , 'R' ], [ 'L' , 'L' , 'L' , 'L' ], [ 'R' , 'R' , 'R' , 'R' ], [ 'L' , 'L' , 'L' , 'L' ]] print (min_cost(grid)) |
3
Time Complexity: O(M * N), where M is the number of rows and N is the number of columns in the input matrix grid[][]
Auxiliary Space: O(M * N)
Contact Us