Given a matrix grid[][] of size N x N, the task is to find the minimum cost required to reach the bottom right corner of the matrix from the top left corner, where the cost of moving to a new cell is [S/2] + K, where S is the score at the previous index and K is the matrix element at the current index.
Note: Here, [X] is the largest integer which is not exceeding X.
Examples:
Input: grid[][] = {{0, 3, 9, 6}, {1, 4, 4, 5}, {8, 2, 5, 4}, {1, 8, 5, 9}}
Output: 12
Explanation: One of the possible set of moves is as follows 0 -> 1 -> 4 -> 4 -> 7 -> 7 -> 12.Input: grid[][] = {{0, 82, 2, 6, 7}, {4, 3, 1, 5, 21}, {6, 4, 20, 2, 8}, {6, 6, 64, 1, 8}, {1, 65, 1, 6, 4}}
Output: 7
Approach: Follow the steps below to solve the problem:
- Make the first element of the matrix zero.
- Traverse in the range [0, N-1]:
- Initialize a list, say moveList, and append the moves i and j.
- Initialize another list, say possibleWays, and append moveList in it.
- Initialize a list, say possibleWaysSum, initially as an empty list.
- Traverse the list possibleWays:
- Traverse the appended moveList:
- Check if the move is equal to i, then update i = i + 1.
- Otherwise, update j = j + 1.
- Initialize a variable, say tempSum. Set tempSum = tempSum + grid[i][j].
- Append tempSum in possibleWays list after the loop.
- Traverse the appended moveList:
- Print the minimum cost from possibleWaysSum as the output.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;vector<vector<char> > possibleWays;// Returns true if str[curr] does not matches with any// of the characters after str[start]bool shouldSwap(char str[], int start, int curr){ for (int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true;}// Function for the swapvoid swap(char str[], int i, int j){ char c = str[i]; str[i] = str[j]; str[j] = c;}// Prints all distinct permutations in str[0..n-1]void findPermutations(char str[], int index, int n){ if (index >= n) { vector<char> l; for (int i = 0; i < n; i++) l.push_back(str[i]); possibleWays.push_back(l); return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] bool check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } }}// Function to print the minimum costvoid minCost(int grid[][5], int N){ vector<char> moveList; // Making top-left value 0 // implicitly to generate list of moves grid[0][0] = 0; vector<int> possibleWaysSum; for (int k = 0; k < N - 1; k++) { moveList.push_back('i'); moveList.push_back('j'); possibleWays.clear(); // Convert into set to make only unique values int n = moveList.size(); char str[n]; for (int i = 0; i < n; i++) str[i] = moveList[i]; // To store the unique permutation of moveList // into the possibleWays findPermutations(str, 0, n); possibleWaysSum.clear(); // Traverse the list for (vector<char> way : possibleWays) { int i = 0, j = 0, tempSum = 0; for (char move : way) { if (move == 'i') { i += 1; } else { j += 1; } // Stores cost according to given // conditions tempSum = (int)(floor(tempSum / 2)) + grid[i][j]; } possibleWaysSum.push_back(tempSum); } } // Print the minimum possible cost int ans = possibleWaysSum[0]; for (int i = 1; i < possibleWaysSum.size(); i++) ans = min(ans, possibleWaysSum[i]); cout << ans;}// Driven Programint main(){ // Size of the grid int N = 4; // Given grid[][] int grid[][5] = { { 0, 3, 9, 6 }, { 1, 4, 4, 5 }, { 8, 2, 5, 4 }, { 1, 8, 5, 9 } }; // Function call to print the minimum // cost to reach bottom-right corner // from the top-left corner of the matrix minCost(grid, N); return 0;}// This code is contributed by Kingash. |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { static ArrayList<ArrayList<Character> > possibleWays; // Returns true if str[curr] does not matches with any // of the characters after str[start] static boolean shouldSwap(char str[], int start, int curr) { for (int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true; } // Prints all distinct permutations in str[0..n-1] static void findPermutations(char str[], int index, int n) { if (index >= n) { ArrayList<Character> l = new ArrayList<>(); for (char ch : str) l.add(ch); possibleWays.add(l); return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] boolean check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } } } // Function for the swap static void swap(char[] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; } // Function to print the minimum cost static void minCost(int grid[][], int N) { ArrayList<Character> moveList = new ArrayList<>(); // Making top-left value 0 // implicitly to generate list of moves grid[0][0] = 0; ArrayList<Integer> possibleWaysSum = new ArrayList<>(); for (int k = 0; k < N - 1; k++) { moveList.add('i'); moveList.add('j'); possibleWays = new ArrayList<>(); // Convert into set to make only unique values int n = moveList.size(); char str[] = new char[n]; for (int i = 0; i < n; i++) str[i] = moveList.get(i); // To store the unique permutation of moveList // into the possibleWays findPermutations(str, 0, n); possibleWaysSum = new ArrayList<>(); // Traverse the list for (ArrayList<Character> way : possibleWays) { int i = 0, j = 0, tempSum = 0; for (char move : way) { if (move == 'i') { i += 1; } else { j += 1; } // Stores cost according to given // conditions tempSum = (int)(Math.floor(tempSum / 2)) + grid[i][j]; } possibleWaysSum.add(tempSum); } } // Print the minimum possible cost int ans = possibleWaysSum.get(0); for (int i = 1; i < possibleWaysSum.size(); i++) ans = Math.min(ans, possibleWaysSum.get(i)); System.out.println(ans); } // Driver code public static void main(String[] args) { // Size of the grid int N = 4; // Given grid[][] int grid[][] = { { 0, 3, 9, 6 }, { 1, 4, 4, 5 }, { 8, 2, 5, 4 }, { 1, 8, 5, 9 } }; // Function call to print the minimum // cost to reach bottom-right corner // from the top-left corner of the matrix minCost(grid, N); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approachfrom itertools import permutationsfrom math import floor# Function to print the minimum costdef minCost(grid, N): moveList = [] # Making top-left value 0 # implicitly to generate list of moves grid[0][0] = 0 for i in range(N - 1): moveList.append('i') moveList.append('j') # Convert into set to make only unique values possibleWays = list(set(permutations(moveList))) possibleWaysSum = [] # Traverse the list for way in possibleWays: i, j, tempSum = 0, 0, 0 for move in way: if move == 'i': i += 1 else: j += 1 # Stores cost according to given conditions tempSum = floor(tempSum/2) + grid[i][j] possibleWaysSum.append(tempSum) minWayIndex = possibleWaysSum.index(min(possibleWaysSum)) # Print the minimum possible cost print(min(possibleWaysSum))# Size of the gridN = 4# Given grid[][]grid = [[0, 3, 9, 6], [1, 4, 4, 5], [8, 2, 5, 4], [1, 8, 5, 9]]# Function call to print the minimum# cost to reach bottom-right corner# from the top-left corner of the matrixminCost(grid, N) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { static List<List<char> > possibleWays; // Returns true if str[curr] does not matches with any // of the chars after str[start] static bool shouldSwap(char[] str, int start, int curr) { for (int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true; } // Prints all distinct permutations in str[0..n-1] static void findPermutations(char[] str, int index, int n) { if (index >= n) { List<char> l = new List<char>(); foreach(char ch in str) l.Add(ch); possibleWays.Add(l); return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the chars // after str[index] bool check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } } } // Function for the swap static void swap(char[] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; } // Function to print the minimum cost static void minCost(int[][] grid, int N) { List<char> moveList = new List<char>(); // Making top-left value 0 // implicitly to generate list of moves grid[0][0] = 0; List<int> possibleWaysSum = new List<int>(); for (int k = 0; k < N - 1; k++) { moveList.Add('i'); moveList.Add('j'); possibleWays = new List<List<char> >(); // Convert into set to make only unique values int n = moveList.Count; char[] str = new char[n]; for (int i = 0; i < n; i++) str[i] = moveList[i]; // To store the unique permutation of moveList // into the possibleWays findPermutations(str, 0, n); possibleWaysSum = new List<int>(); // Traverse the list foreach(List<char> way in possibleWays) { int i = 0, j = 0, tempSum = 0; foreach(char move in way) { if (move == 'i') { i += 1; } else { j += 1; } // Stores cost according to given // conditions tempSum = (int)(tempSum / 2) + grid[i][j]; } possibleWaysSum.Add(tempSum); } } // Print the minimum possible cost int ans = possibleWaysSum[0]; for (int i = 1; i < possibleWaysSum.Count; i++) ans = Math.Min(ans, possibleWaysSum[i]); Console.WriteLine(ans); } // Driver code public static void Main(string[] args) { // Size of the grid int N = 4; // Given grid[][] int[][] grid = { new[] { 0, 3, 9, 6 }, new[] { 1, 4, 4, 5 }, new[] { 8, 2, 5, 4 }, new[] { 1, 8, 5, 9 } }; // Function call to print the minimum // cost to reach bottom-right corner // from the top-left corner of the matrix minCost(grid, N); }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript program for the above approachlet possibleWays = [];// Returns true if str[curr] does not matches with any// of the characters after str[start]function shouldSwap(str, start, curr) { for (let i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true;}// Prints all distinct permutations in str[0..n-1]function findPermutations(str, index, n) { if (index >= n) { let l = new Array(); for (let ch of str) l.push(ch); possibleWays.push(l); return; } for (let i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] let check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } }}// Function for the swapfunction swap(str, i, j) { let c = str[i]; str[i] = str[j]; str[j] = c;}// Function to print the minimum costfunction minCost(grid, N) { let moveList = new Array(); // Making top-left value 0 // implicitly to generate list of moves grid[0][0] = 0; let possibleWaysSum = new Array(); for (let k = 0; k < N - 1; k++) { moveList.push('i'); moveList.push('j'); possibleWays = new Array(); // Convert into set to make only unique values let n = moveList.length; let str = []; for (let i = 0; i < n; i++) str[i] = moveList[i]; // To store the unique permutation of moveList // into the possibleWays findPermutations(str, 0, n); possibleWaysSum = new Array(); // Traverse the list for (let way of possibleWays) { let i = 0, j = 0, tempSum = 0; for (let move of way) { if (move == 'i') { i += 1; } else { j += 1; } // Stores cost according to given // conditions tempSum = (Math.floor(tempSum / 2)) + grid[i][j]; } possibleWaysSum.push(tempSum); } } // Print the minimum possible cost let ans = possibleWaysSum[0]; for (let i = 1; i < possibleWaysSum.length; i++) ans = Math.min(ans, possibleWaysSum[i]); document.write(ans);}// Driver code// Size of the gridlet N = 4;// Given grid[][]let grid = [[0, 3, 9, 6],[1, 4, 4, 5],[8, 2, 5, 4],[1, 8, 5, 9]];// Function call to print the minimum// cost to reach bottom-right corner// from the top-left corner of the matrixminCost(grid, N);// This code is contributed by Saurabh Jaiswal</script> |
Output:
12
Time Complexity: O(N2)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
