Minimum cost to reach from the top-left to the bottom-right corner of a matrix
Given an N * M matrix mat[][] consisting of lower case characters, the task is to find the minimum cost to reach from the cell mat[0][0] to the cell mat[N-1][M-1]. If you are at a cell mat[i][j], you can jump to the cells mat[i+1][j], mat[i][j+1], mat[i-1][j], mat[i][j-1] (without going out of bounds) with a cost of 1. Additionally, you can jump to any cell mat[m][n] such that mat[n][m] = mat[i][j] with a cost of 0.
Examples:
Input: mat[][] = {“abc”, “efg”, “hij”}
Output: 4
One of the shortest path will be:
{0, 0} -> {0, 1} -> {0, 2} -> {1, 2} -> {2, 2}
All the edges have a weight of 1, thus the answer is 4.
Input: mat[][] = {“abc”, “efg”, “hbj”}
Output: 2
{0, 0} -> {0, 1} -> {2, 1} -> {2, 2}
1 + 0 + 1 = 2
Naive approach: One approach for solving this problem will be 0-1 BFS. Visualise the setup as a graph with N * M nodes. All the nodes will be connected to adjacent nodes with an edge of weight 1 and the nodes with the same characters with an edge with weight 0. Now, BFS can be used to find the shortest path from the cell mat[0][0] to the cell mat[N-1][M-1]. The time complexity of this will be O((N * M)2) because the number of edges will be of the order O((N * M)2).
Efficient approach: For each character X, find all the characters it is adjacent to. Now, create a graph with a number of nodes as the number of distinct characters in the string each representing a character.
Each node X will have an edge of weight 1 with all the nodes representing the characters adjacent to the character X in the real graph. Then a BFS can be run from the node representing mat[0][0] to the node representing mat[N-1][M-1] in this new graph. The time complexity of this approach will be O(N * M) for pre-processing the graph and the time complexity for running the BFS can be considered constant.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 26;// Function to return// the value (x - 97)int f(int x){ return x - 'a';}// Function to return the minimum costint findMinCost(vector<string> arr){ int n = arr.size(); int m = arr[0].size(); // Graph vector<vector<int> > gr(MAX); // Adjacency matrix bool edge[MAX][MAX]; // Initialising the adjacency matrix for (int k = 0; k < MAX; k++) for (int l = 0; l < MAX; l++) edge[k][l] = 0; // Creating the adjacency matrix for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (i + 1 < n and !edge[f(arr[i][j])][f(arr[i + 1][j])]) { gr[f(arr[i][j])].push_back(f(arr[i + 1][j])); edge[f(arr[i][j])][f(arr[i + 1][j])] = 1; } if (j - 1 >= 0 and !edge[f(arr[i][j])][f(arr[i][j - 1])]) { gr[f(arr[i][j])].push_back(f(arr[i][j - 1])); edge[f(arr[i][j])][f(arr[i][j - 1])] = 1; } if (j + 1 < m and !edge[f(arr[i][j])][f(arr[i][j + 1])]) { gr[f(arr[i][j])].push_back(f(arr[i][j + 1])); edge[f(arr[i][j])][f(arr[i][j + 1])] = 1; } if (i - 1 >= 0 and !edge[f(arr[i][j])][f(arr[i - 1][j])]) { gr[f(arr[i][j])].push_back(f(arr[i - 1][j])); edge[f(arr[i][j])][f(arr[i - 1][j])] = 1; } } // Queue to perform BFS queue<int> q; q.push(arr[0][0] - 'a'); // Visited array bool v[MAX] = { 0 }; // To store the depth of BFS int d = 0; // BFS while (q.size()) { // Number of elements in // the current level int cnt = q.size(); // Inner loop while (cnt--) { // Current element int curr = q.front(); // Popping queue q.pop(); // If the current node has // already been visited if (v[curr]) continue; v[curr] = 1; // Checking if the current // node is the required node if (curr == arr[n - 1][m - 1] - 'a') return d; // Iterating through the current node for (auto it : gr[curr]) q.push(it); } // Updating the depth d++; } return -1;}// Driver codeint main(){ vector<string> arr = { "abc", "def", "gbi" }; cout << findMinCost(arr); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { static int MAX = 26; // Function to return // the value (x - 97) static int f(int x) { return x - 'a'; } // Function to return the minimum cost static int findMinCost(String[] arr) { int n = arr.length; int m = arr[0].length(); // Graph Vector<Integer>[] gr = new Vector[MAX]; for (int i = 0; i < MAX; i++) gr[i] = new Vector<Integer>(); // Adjacency matrix boolean[][] edge = new boolean[MAX][MAX]; // Initialising the adjacency matrix for (int k = 0; k < MAX; k++) for (int l = 0; l < MAX; l++) edge[k][l] = false; // Creating the adjacency matrix for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (i + 1 < n && !edge[f(arr[i].charAt(j))][f(arr[i + 1].charAt(j))]) { gr[f(arr[i].charAt(j))].add(f(arr[i + 1].charAt(j))); edge[f(arr[i].charAt(j))][f(arr[i + 1].charAt(j))] = true; } if (j - 1 >= 0 && !edge[f(arr[i].charAt(j))][f(arr[i].charAt(j - 1))]) { gr[f(arr[i].charAt(j))].add(f(arr[i].charAt(j - 1))); edge[f(arr[i].charAt(j))][f(arr[i].charAt(j - 1))] = true; } if (j + 1 < m && !edge[f(arr[i].charAt(j))][f(arr[i].charAt(j + 1))]) { gr[f(arr[i].charAt(j))].add(f(arr[i].charAt(j + 1))); edge[f(arr[i].charAt(j))][f(arr[i].charAt(j + 1))] = true; } if (i - 1 >= 0 && !edge[f(arr[i].charAt(j))][f(arr[i - 1].charAt(j))]) { gr[f(arr[i].charAt(j))].add(f(arr[i - 1].charAt(j))); edge[f(arr[i].charAt(j))][f(arr[i - 1].charAt(j))] = true; } } // Queue to perform BFS Queue<Integer> q = new LinkedList<Integer>(); q.add(arr[0].charAt(0) - 'a'); // Visited array boolean[] v = new boolean[MAX]; // To store the depth of BFS int d = 0; // BFS while (q.size() > 0) { // Number of elements in // the current level int cnt = q.size(); // Inner loop while (cnt-- > 0) { // Current element int curr = q.peek(); // Popping queue q.remove(); // If the current node has // already been visited if (v[curr]) continue; v[curr] = true; // Checking if the current // node is the required node if (curr == arr[n - 1].charAt(m - 1) - 'a') return d; // Iterating through the current node for (Integer it : gr[curr]) q.add(it); } // Updating the depth d++; } return -1; } // Driver code public static void main(String[] args) { String[] arr = { "abc", "def", "gbi" }; System.out.print(findMinCost(arr)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachMAX = 26# Function to return# the value (x - 97)def f(x): return ord(x) - ord('a')# Function to return the minimum costdef findMinCost( arr): global MAX n = len(arr) m = len(arr[0]) # Graph gr = [] for x in range(MAX): gr.append([]) # Adjacency matrix edge = [] # Initialising the adjacency matrix for k in range(MAX): edge.append([]) for l in range(MAX): edge[k].append(0) # Creating the adjacency matrix for i in range(n): for j in range(m): if (i + 1 < n and edge[f(arr[i][j])][f(arr[i + 1][j])] == 0): gr[f(arr[i][j])].append(f(arr[i + 1][j])) edge[f(arr[i][j])][f(arr[i + 1][j])] = 1 if (j - 1 >= 0 and edge[f(arr[i][j])][f(arr[i][j - 1])] == 0): gr[f(arr[i][j])].append(f(arr[i][j - 1])) edge[f(arr[i][j])][f(arr[i][j - 1])] = 1 if (j + 1 < m and edge[f(arr[i][j])][f(arr[i][j + 1])] == 0): gr[f(arr[i][j])].append(f(arr[i][j + 1])) edge[f(arr[i][j])][f(arr[i][j + 1])] = 1 if (i - 1 >= 0 and edge[f(arr[i][j])][f(arr[i - 1][j])] == 0): gr[f(arr[i][j])].append(f(arr[i - 1][j])) edge[f(arr[i][j])][f(arr[i - 1][j])] = 1 # Queue to perform BFS q = [] q.append(ord(arr[0][0]) - ord('a')) # Visited array v = [] for i in range(MAX): v.append(0) # To store the depth of BFS d = 0 # BFS while (len(q) > 0): # Number of elements in # the current level cnt = len(q) # Inner loop while (cnt > 0): cnt = cnt - 1 # Current element curr = q[0] # Popping queue q.pop(0) # If the current node has # already been visited if (v[curr] != 0): continue v[curr] = 1 # Checking if the current # node is the required node if (curr == (ord(arr[n - 1][m - 1]) - ord('a'))): return d # Iterating through the current node for it in gr[curr]: q.append(it) # Updating the depth d = d + 1 return -1# Driver codearr =[ "abc","def","gbi" ]print( findMinCost(arr))# This code is contributed by Arnab Kundu |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG { static int MAX = 26; // Function to return // the value (x - 97) static int f(int x) { return x - 'a'; } // Function to return the minimum cost static int findMinCost(String[] arr) { int n = arr.Length; int m = arr[0].Length; // Graph List<int>[] gr = new List<int>[MAX]; for (int i = 0; i < MAX; i++) gr[i] = new List<int>(); // Adjacency matrix bool[,] edge = new bool[MAX, MAX]; // Initialising the adjacency matrix for (int k = 0; k < MAX; k++) for (int l = 0; l < MAX; l++) edge[k,l] = false; // Creating the adjacency matrix for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (i + 1 < n && !edge[f(arr[i][j]),f(arr[i + 1][j])]) { gr[f(arr[i][j])].Add(f(arr[i + 1][j])); edge[f(arr[i][j]), f(arr[i + 1][j])] = true; } if (j - 1 >= 0 && !edge[f(arr[i][j]),f(arr[i][j - 1])]) { gr[f(arr[i][j])].Add(f(arr[i][j - 1])); edge[f(arr[i][j]), f(arr[i][j - 1])] = true; } if (j + 1 < m && !edge[f(arr[i][j]),f(arr[i][j + 1])]) { gr[f(arr[i][j])].Add(f(arr[i][j + 1])); edge[f(arr[i][j]), f(arr[i][j + 1])] = true; } if (i - 1 >= 0 && !edge[f(arr[i][j]),f(arr[i - 1][j])]) { gr[f(arr[i][j])].Add(f(arr[i - 1][j])); edge[f(arr[i][j]), f(arr[i - 1][j])] = true; } } // Queue to perform BFS Queue<int> q = new Queue<int>(); q.Enqueue(arr[0][0] - 'a'); // Visited array bool[] v = new bool[MAX]; // To store the depth of BFS int d = 0; // BFS while (q.Count > 0) { // Number of elements in // the current level int cnt = q.Count; // Inner loop while (cnt-- > 0) { // Current element int curr = q.Peek(); // Popping queue q.Dequeue(); // If the current node has // already been visited if (v[curr]) continue; v[curr] = true; // Checking if the current // node is the required node if (curr == arr[n - 1][m - 1] - 'a') return d; // Iterating through the current node foreach (int it in gr[curr]) q.Enqueue(it); } // Updating the depth d++; } return -1; } // Driver code public static void Main(String[] args) { String[] arr = { "abc", "def", "gbi" }; Console.Write(findMinCost(arr)); }}// This code is contributed by 29AjayKumar |
Javascript
// Javascript implementation of the approachconst MAX = 26;// Function to return the value (x - 97)function f(x) { return x.charCodeAt(0) - 'a'.charCodeAt(0);}// Function to return the minimum costfunction findMinCost(arr) { let n = arr.length; let m = arr[0].length; // Graph let gr = []; for (let x = 0; x < MAX; x++) { gr.push([]); } // Adjacency matrix let edge = []; // Initializing the adjacency matrix for (let k = 0; k < MAX; k++) { edge.push([]); for (let l = 0; l < MAX; l++) { edge[k].push(0); } } // Creating the adjacency matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (i + 1 < n && edge[f(arr[i][j])][f(arr[i + 1][j])] === 0) { gr[f(arr[i][j])].push(f(arr[i + 1][j])); edge[f(arr[i][j])][f(arr[i + 1][j])] = 1; } if (j - 1 >= 0 && edge[f(arr[i][j])][f(arr[i][j - 1])] === 0) { gr[f(arr[i][j])].push(f(arr[i][j - 1])); edge[f(arr[i][j])][f(arr[i][j - 1])] = 1; } if (j + 1 < m && edge[f(arr[i][j])][f(arr[i][j + 1])] === 0) { gr[f(arr[i][j])].push(f(arr[i][j + 1])); edge[f(arr[i][j])][f(arr[i][j + 1])] = 1; } if (i - 1 >= 0 && edge[f(arr[i][j])][f(arr[i - 1][j])] === 0) { gr[f(arr[i][j])].push(f(arr[i - 1][j])); edge[f(arr[i][j])][f(arr[i - 1][j])] = 1; } } } // Queue to perform BFS let q = []; q.push(arr[0][0].charCodeAt(0) - 'a'.charCodeAt(0)); // Visited array let v = []; for (let i = 0; i < MAX; i++) { v.push(0); } // To store the depth of BFS let d = 0;// BFSwhile (q.length > 0) {// Number of elements in the current levellet cnt = q.length;// Inner loopwhile (cnt > 0) {cnt--;// Current elementlet curr = q[0];// Popping queueq.shift();// If the current node has already been visitedif (v[curr] !== 0) continue;v[curr] = 1;// Checking if the current node is the required nodeif (curr === (arr[n - 1][m - 1].charCodeAt(0) - 'a'.charCodeAt(0))) return d;// Iterating through the current nodefor (let it of gr[curr]) { q.push(it);}}// Updating the depthd++;}return -1;};// Driver codelet arr = ['abc', 'def', 'gbi'];console.log(findMinCost(arr)); |
Output:
2
Time Complexity: O(N * M).
Auxiliary Space: O(N * M).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
