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

MinimumCostPath

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

Output

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) 




Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Optimal Construction of Roads Optimal Construction of Roads
Maximize the number of boxes using red and yellow balls Maximize the number of boxes using red and yellow balls
Maximize number of indices with prefix sum equal to 0 Maximize number of indices with prefix sum equal to 0
Number of pairs of words not in correct order Number of pairs of words not in correct order
Check matrix transformation by flipping sub-matrices along the principal or anti-diagonal Check matrix transformation by flipping sub-matrices along the principal or anti-diagonal

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje