Minimum Cost to reach the end of the matrix
Given a matrix of size N X N, such that each cell has an Uppercase Character in it, find the minimum cost to reach the cell (N-1, N-1) starting from (0, 0). From a cell (i, j), we can move Up(i-1, j), Down(i+1, j), Left (i, j-1) and Right(i, j+1). If the adjacent cell has the same character as the current cell then we can move to the adjacent cell with 0 cost, else the cost incurred is 1 coin.
Examples:
Input: m = 2, n = 3, mat = { { βaβ, βbβ, βnβ }, { βdβ, βeβ, βfβ } }
Output: 3
Explanation: One of the possible answers is to move from βaβ -> βbβ -> βeβ -> βfβ with the cost of 1 + 1 + 1 = 3Input: m = 2, n = 2, mat = {{βaβ, βaβ}, {βaβ, βaβ}}
Output: 0
Explanation: We can take any path from the top left to the bottom right as the cost is always zero.
Approach: To solve the problem follow the below idea:
The idea is to use Breadth-First Search (BFS) to find the shortest path from the top-left corner to the bottom-right corner of a matrix. Determine the character in each cell, where moving to an adjacent cell with the same character incurs a 0 cost, and moving to a different character incurs a cost of 1 coin. The distance matrix is updated during BFS to keep track of the minimum cost to reach each cell. The code then initializes the matrix, performs BFS, and outputs the minimum cost to reach the destination.
Step-by-step approach:
- Initialize a distance matrix (dis[][]) with large values (INF).
- Start BFS from the top-left corner (cell (0, 0)).
- Use a deque (dq) to store cells to be processed.
- For each cell in the deque, explore its neighbors (up, down, left, right).
- Update the distance matrix dis[][] based on the cost of moving to the neighbor (0 or 1 coin).
- Push the neighbor to the front of the deque if the character of the neighbor is same as the current cell otherwise push it to the back of the deque.
- Finally, return the answer as dis[m-1][n-1]
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; #define INF 100000000 #define in_range(x, y, m, n) \ (x >= 0 && x < m && y >= 0 && y < n) char mat[1000][1000]; int dis[1000][1000]; // Initialize the distance matrix with INF values void init( int m, int n) { for ( int i = 0; i < m; i++) for ( int j = 0; j < n; j++) dis[i][j] = INF; } // Perform Breadth-First Search to find the shortest path void bfs( int startX, int startY, int m, int n) { dis[startX][startY] = 0; deque<pair< int , int > > dq; pair< int , int > p; dq.push_front(make_pair(startX, startY)); // BFS traversal while (!dq.empty()) { p = dq.front(); dq.pop_front(); int x = p.first; int y = p.second; int a[] = { 0, -1, 0, 1 }, b[] = { -1, 0, 1, 0 }; // Explore neighbors for ( int i = 0; i < 4; i++) { int tempX = x + a[i]; int tempY = y + b[i]; // Check if the neighbor is within the matrix // bounds if (in_range(tempX, tempY, m, n)) { // If the neighbor has the same character // and a shorter distance, update and add to // the front of the queue if (mat[tempX][tempY] == mat[x][y] && dis[tempX][tempY] > dis[x][y]) { dq.push_front(make_pair(tempX, tempY)); dis[tempX][tempY] = dis[x][y]; } // If the neighbor has a different character // and a shorter distance, update and add to // the back of the queue else if (mat[tempX][tempY] != mat[x][y]) { if (dis[tempX][tempY] > dis[x][y] + 1) { dq.push_back( make_pair(tempX, tempY)); dis[tempX][tempY] = dis[x][y] + 1; } } } } } } // Display the matrix and distance matrix void display( int m, int n) { // Display the matrix cout << "Matrix:\n"; for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { cout << mat[i][j] << " "; } cout << endl; } // Display the distance matrix cout << "Distance Matrix:\n"; for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { cout << dis[i][j] << " "; } cout << endl; } } int main() { // Static input int m = 2, n = 3; char matStatic[2][3] = { { 'a' , 'b' , 'n' }, { 'd' , 'e' , 'f' } }; // Copy the static input to the global matrix for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { mat[i][j] = matStatic[i][j]; } } // Initialize and perform BFS init(m, n); bfs(0, 0, m, n); // Output the result cout << "Shortest Path Distance: " << dis[m - 1][n - 1] << endl; return 0; } |
Java
import java.util.ArrayDeque; import java.util.Deque; class ShortestPathBFS { static final int INF = 100000000 ; static char [][] mat = new char [ 1000 ][ 1000 ]; static int [][] dis = new int [ 1000 ][ 1000 ]; static boolean inRange( int x, int y, int m, int n) { return x >= 0 && x < m && y >= 0 && y < n; } // Initialize the distance matrix with INF values static void init( int m, int n) { for ( int i = 0 ; i < m; i++) for ( int j = 0 ; j < n; j++) dis[i][j] = INF; } // Perform Breadth-First Search to find the shortest // path static void bfs( int startX, int startY, int m, int n) { dis[startX][startY] = 0 ; Deque< int []> dq = new ArrayDeque<>(); int [] p = { startX, startY }; dq.addFirst(p); // BFS traversal while (!dq.isEmpty()) { p = dq.pollFirst(); int x = p[ 0 ]; int y = p[ 1 ]; int [] a = { 0 , - 1 , 0 , 1 }, b = { - 1 , 0 , 1 , 0 }; // Explore neighbors for ( int i = 0 ; i < 4 ; i++) { int tempX = x + a[i]; int tempY = y + b[i]; // Check if the neighbor is within the // matrix bounds if (inRange(tempX, tempY, m, n)) { // If the neighbor has the same // character and a shorter distance, // update and add to the front of the // queue if (mat[tempX][tempY] == mat[x][y] && dis[tempX][tempY] > dis[x][y]) { dq.addFirst( new int [] { tempX, tempY }); dis[tempX][tempY] = dis[x][y]; } // If the neighbor has a different // character and a shorter distance, // update and add to the back of the // queue else if (mat[tempX][tempY] != mat[x][y]) { if (dis[tempX][tempY] > dis[x][y] + 1 ) { dq.addLast( new int [] { tempX, tempY }); dis[tempX][tempY] = dis[x][y] + 1 ; } } } } } } // Display the matrix and distance matrix static void display( int m, int n) { System.out.println( "Matrix:" ); for ( int i = 0 ; i < m; i++) { for ( int j = 0 ; j < n; j++) { System.out.print(mat[i][j] + " " ); } System.out.println(); } System.out.println( "Distance Matrix:" ); for ( int i = 0 ; i < m; i++) { for ( int j = 0 ; j < n; j++) { System.out.print(dis[i][j] + " " ); } System.out.println(); } } public static void main(String[] args) { int m = 2 , n = 3 ; char [][] matStatic = { { 'a' , 'b' , 'n' }, { 'd' , 'e' , 'f' } }; for ( int i = 0 ; i < m; i++) { for ( int j = 0 ; j < n; j++) { mat[i][j] = matStatic[i][j]; } } // Initialize and perform BFS init(m, n); bfs( 0 , 0 , m, n); // Output the result System.out.println( "Shortest Path Distance: " + dis[m - 1 ][n - 1 ]); } } |
Python3
from collections import deque INF = 10 * * 9 # Initialize the distance matrix with INF values def init(m, n): return [[INF for _ in range (n)] for _ in range (m)] # Perform Breadth-First Search to find the shortest path def bfs(startX, startY, mat, dis): dis[startX][startY] = 0 dq = deque([(startX, startY)]) dirs = [( 0 , - 1 ), ( - 1 , 0 ), ( 0 , 1 ), ( 1 , 0 )] # BFS traversal while dq: x, y = dq.popleft() # Explore neighbors for dx, dy in dirs: tempX, tempY = x + dx, y + dy # Check if the neighbor is within the matrix bounds if 0 < = tempX < len (mat) and 0 < = tempY < len (mat[ 0 ]): # If the neighbor has the same character and a shorter distance, # update and add to the front of the queue if mat[tempX][tempY] = = mat[x][y] and dis[tempX][tempY] > dis[x][y]: dq.appendleft((tempX, tempY)) dis[tempX][tempY] = dis[x][y] # If the neighbor has a different character and a shorter distance, # update and add to the back of the queue elif mat[tempX][tempY] ! = mat[x][y]: if dis[tempX][tempY] > dis[x][y] + 1 : dq.append((tempX, tempY)) dis[tempX][tempY] = dis[x][y] + 1 # Display the matrix and distance matrix def display(mat, dis): # Display the matrix print ( "Matrix:" ) for row in mat: print ( " " .join(row)) # Display the distance matrix print ( "Distance Matrix:" ) for row in dis: print ( " " .join( map ( str , row))) # Driver code if __name__ = = "__main__" : # Static input m, n = 2 , 3 mat = [[ 'a' , 'b' , 'n' ], [ 'd' , 'e' , 'f' ]] # Initialize and perform BFS dis = init(m, n) bfs( 0 , 0 , mat, dis) # Output the result print ( "Shortest Path Distance:" , dis[m - 1 ][n - 1 ]) |
C#
using System; using System.Collections.Generic; class Program { const int INF = 100000000; static char [,] mat = new char [1000, 1000]; static int [,] dis = new int [1000, 1000]; // Initialize the distance matrix with INF values static void Init( int m, int n) { for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { dis[i, j] = INF; } } } // Perform Breadth-First Search to find the shortest path static void BFS( int startX, int startY, int m, int n) { dis[startX, startY] = 0; Queue<Tuple< int , int >> dq = new Queue<Tuple< int , int >>(); Tuple< int , int > p = Tuple.Create(startX, startY); dq.Enqueue(p); // BFS traversal while (dq.Count > 0) { p = dq.Dequeue(); int x = p.Item1; int y = p.Item2; int [] a = { 0, -1, 0, 1 }; int [] b = { -1, 0, 1, 0 }; // Explore neighbors for ( int i = 0; i < 4; i++) { int tempX = x + a[i]; int tempY = y + b[i]; // Check if the neighbor is within the matrix bounds if (InRange(tempX, tempY, m, n)) { // If the neighbor has the same character and a shorter distance, update and add to // the front of the queue if (mat[tempX, tempY] == mat[x, y] && dis[tempX, tempY] > dis[x, y]) { dq.Enqueue(Tuple.Create(tempX, tempY)); dis[tempX, tempY] = dis[x, y]; } // If the neighbor has a different character and a shorter distance, update and add to // the back of the queue else if (mat[tempX, tempY] != mat[x, y]) { if (dis[tempX, tempY] > dis[x, y] + 1) { dq.Enqueue(Tuple.Create(tempX, tempY)); dis[tempX, tempY] = dis[x, y] + 1; } } } } } } // Check if the position is within the matrix bounds static bool InRange( int x, int y, int m, int n) { return x >= 0 && x < m && y >= 0 && y < n; } // Display the matrix and distance matrix static void Display( int m, int n) { // Display the matrix Console.WriteLine( "Matrix:" ); for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { Console.Write(mat[i, j] + " " ); } Console.WriteLine(); } // Display the distance matrix Console.WriteLine( "Distance Matrix:" ); for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { Console.Write(dis[i, j] + " " ); } Console.WriteLine(); } } static void Main() { // Static input int m = 2, n = 3; char [,] matStatic = { { 'a' , 'b' , 'n' }, { 'd' , 'e' , 'f' } }; // Copy the static input to the global matrix for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { mat[i, j] = matStatic[i, j]; } } // Initialize and perform BFS Init(m, n); BFS(0, 0, m, n); // Output the result Console.WriteLine( "Shortest Path Distance: " + dis[m - 1, n - 1]); } } // This code is contributed by shivamgupta0987654321 |
Javascript
// javaScript code for the above approach const INF = 100000000; // Function to check if a cell is within the matrix bounds function inRange(x, y, m, n) { return x >= 0 && x < m && y >= 0 && y < n; } const mat = []; const dis = []; // Initialize the distance matrix with INF values function init(m, n) { for (let i = 0; i < m; i++) { mat.push( new Array(n).fill( '' )); dis.push( new Array(n).fill(INF)); } } // Perform Breadth-First Search to find the shortest path function bfs(startX, startY, m, n) { dis[startX][startY] = 0; const dq = []; dq.push([startX, startY]); // BFS traversal while (dq.length > 0) { const [x, y] = dq.shift(); const a = [0, -1, 0, 1]; const b = [-1, 0, 1, 0]; // Explore neighbors for (let i = 0; i < 4; i++) { const tempX = x + a[i]; const tempY = y + b[i]; // Check if the neighbor is within the matrix bounds if (inRange(tempX, tempY, m, n)) { // If the neighbor has the same character // and a shorter distance, update and add to // the front of the queue if (mat[tempX][tempY] === mat[x][y] && dis[tempX][tempY] > dis[x][y]) { dq.unshift([tempX, tempY]); dis[tempX][tempY] = dis[x][y]; } // If the neighbor has a different character // and a shorter distance, update and add to // the back of the queue else if (mat[tempX][tempY] !== mat[x][y]) { if (dis[tempX][tempY] > dis[x][y] + 1) { dq.push([tempX, tempY]); dis[tempX][tempY] = dis[x][y] + 1; } } } } } } // Display the matrix and distance matrix function display(m, n) { // Display the matrix console.log( "Matrix:" ); for (let i = 0; i < m; i++) { console.log(mat[i].join( ' ' )); } // Display the distance matrix console.log( "Distance Matrix:" ); for (let i = 0; i < m; i++) { console.log(dis[i].join( ' ' )); } } // Driver code // Static input const m = 2, n = 3; const matStatic = [ [ 'a' , 'b' , 'n' ], [ 'd' , 'e' , 'f' ] ]; // Initialize and perform BFS init(m, n); // Copy the static input to the global matrix for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { mat[i][j] = matStatic[i][j]; } } bfs(0, 0, m, n); // Output the result console.log( "Shortest Path Distance:" , dis[m - 1][n - 1]); |
Shortest Path Distance: 3
Time Complexity: O(m * n), where βmβ is the number of rows and βnβ is the number of columns in the matrix.
Auxiliary Space: O(m * n)