Maximum coin in minimum time by skipping K obstacles along path in Matrix
Given a 2D matrix, where β*β represents an obstacle and the rest all represent coins in the grid. It is also given that you are currently on grid[i1][ j1] and want to reach grid[i2][j2] by skipping at most K obstacles in the path, the task is to collect the maximum coin while reaching grid[i2][j2] in a minimum amount of time.
Note: Only movements in right, left, up or down is allowed.
Examples:
Input: i1 = 0, j1 = 2, i2 = 3, j2 = 3, k = 1
grid = { { β*β, β0β, β1β, β1β },
{ β0β, β0β, β*β, β*β },
{ β0β, β*β, β*β, β*β },
{ β0β, β0β, β0β, β1β } };
Output: 2
Explanation: The path is {0, 2}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {3, 2} and {3, 3}.Input: i1 = 0, j1 = 2, i2 = 3, j2 = 3, k = 2
grid = { { β*β, β0β, β1β, β2β },
{ β0β, β0β, β*β, β*β },
{ β0β, β*β, β6β, β*β },
{ β0β, β0β, β0β, β1β } };
Output: 8
An approach using BFS:
The idea is to use BFS algorithm to reach from start to destination and maintain a variable kLeft which state how many kβs are remaining till any cell and a variable currCoinCollect to represent how many coins are collected till any cell.
Once we reach at destination the time will be minimum [BFS ensures that because of level wise traversal]. Now we will only need to find the maximum amount of coin collected till now.
Follow the steps below to implement the above idea:
- Initialize an array visited for keeping any cell is visited or not. The dimension would be 3D (2D for cell coordinate and one extra dimension for keeping track of βKβ remaining) for keeping track of visiting any cell.
- Initialize a queue for BFS which will store {i, j, kLeft, coinCollected} for the cell in the grid.
- Initialize a variable coinCollect, to store the coin collected to reach the destination in minimum time.
- Initially, Push { i1, j1, k, grid[i1][j1] β β0β } in the queue and mark the current position {i, j} with k remaining visited.
- Initialize a variable minTime for storing the minimum time to reach the destination.
- While the queue is not empty, do the following:
- Calculate the size of the queue and run a loop till the size of the queue.
- Pop the front element from the queue.
- Check if time ? minTime as this ensures that time has exceeded the minimum time to reach the destination:
- Explore all the directions for the current cell say, newX, newY
- Check if the new cell is an obstacle and any k move we have left to cross this obstacle.
- If true, then push { newX, newY, kLeft β 1, currCoinCollect } into the queue and make visited[newX][newY] = true
- If grid[newX][newY] is not an obstacle then push {newX, newY, kLeft, currCoinCollect + (grid[newX][newY] β β0β} into the queue and mark visited[newX][newY][grid[newX][newY] == β*β ? kLeft β 1 : kLeft] = true.
- Check if the new cell is an obstacle and any k move we have left to cross this obstacle.
- Incrementing the time taken after every level
- Finally, return the maximum number of coins collected.
Follow the steps below to implement the above idea:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find all the coin from the // grid in minimum number of time int collectAllCoin(vector<vector< char > >& grid, int i1, int j1, int i2, int j2, int k) { int m = grid.size(), n = grid[0].size(); // For storing the i, j index is // visited or not bool visited[m][n][k + 1] = { false }; // For BFS queue<vector< int > > q; // <val, x, y> // Final coin collect to reach // destination in minimum time. int coinCollect = 0; // Pushing the current position q.push({ i1, j1, k, grid[i1][j1] - '0' }); // Marking the current // position visited visited[i1][j1][k] = true ; // Possible direction to move vector<vector< int > > dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // For counting the current // time while moving int time = 0; // Storing the minimum time to // reach at destination int minTime = INT_MAX; while (q.size() > 0) { int size = q.size(); // This ensure that time has // reached greater than minimum // time to reach at destination if ( time >= minTime) { break ; } for ( int i = 0; i < size; i++) { auto curr = q.front(); q.pop(); int x = curr[0], y = curr[1], kLeft = curr[2], currCoinCollect = curr[3]; if (x == i2 && y == j2) { minTime = min( time , minTime); coinCollect = max(coinCollect, currCoinCollect); } // Explore all the direction for ( int k = 0; k < 4; k++) { int newX = x + dir[k][0]; int newY = y + dir[k][1]; if (newX >= 0 && newX < m && newY >= 0 && newY < n && visited[newX][newY] [grid[newX][newY] == '*' ? kLeft - 1 : kLeft] == false ) { // Check if new cell is // obstacle and any k // move we have left to // cross this obstacle if (grid[newX][newY] == '*' && kLeft > 0) { q.push({ newX, newY, kLeft - 1, currCoinCollect }); } else if (grid[newX][newY] != '*' ) { q.push({ newX, newY, kLeft, currCoinCollect + (grid[newX][newY] - '0' ) }); } if (newX != i2 && newY != j2) visited[newX][newY] [grid[newX][newY] == '*' ? kLeft - 1 : kLeft] = true ; } } } // Incrementing the time taken // after every level time ++; } // Return the total amount of time // taken to collect all the coin return coinCollect / 2; } // Driver code int main() { vector<vector< char > > grid = { { '*' , '0' , '1' , '2' }, { '0' , '0' , '*' , '*' }, { '*' , '*' , '6' , '8' }, { '0' , '0' , '0' , '1' } }; int i1 = 0, j1 = 2; int i2 = 3, j2 = 3; int K = 1; // Function call int maxCoinCollected = collectAllCoin(grid, i1, j1, i2, j2, K); cout << maxCoinCollected << endl; return 0; } |
Python3
# Python code to implement the approach from queue import Queue from sys import maxsize # Function to find all the coin from the # grid in minimum number of time def collectAllCoin(grid, i1, j1, i2, j2, k): m = len (grid) n = len (grid[ 0 ]) # For storing the i, j index is # visited or not visited = [[[ False for _ in range (k + 1 )] for _ in range (n)] for _ in range (m)] # For BFS q = Queue() # <val, x, y> # Final coin collect to reach # destination in minimum time. coinCollect = 0 # Pushing the current position q.put([i1, j1, k, int (grid[i1][j1])]) # Marking the current # position visited visited[i1][j1][k] = True # Possible direction to move dir = [[ 1 , 0 ], [ 0 , 1 ], [ - 1 , 0 ], [ 0 , - 1 ]] # For counting the current # time while moving time = 0 # Storing the minimum time to # reach at destination minTime = maxsize while not q.empty(): size = q.qsize() # This ensure that time has # reached greater than minimum # time to reach at destination if time > = minTime: break for i in range (size): curr = q.get() x, y, kLeft, currCoinCollect = curr if x = = i2 and y = = j2: minTime = min (time, minTime) coinCollect = max (coinCollect, currCoinCollect) # Explore all the direction for k in range ( 4 ): newX = x + dir [k][ 0 ] newY = y + dir [k][ 1 ] if (newX > = 0 and newX < m and newY > = 0 and newY < n and not visited[newX][newY][kLeft - int (grid[newX][newY] = = '*' )]): # Check if new cell is # obstacle and any k # move we have left to # cross this obstacle if (grid[newX][newY] = = '*' and kLeft > 0 ): q.put([newX, newY, kLeft - 1 , currCoinCollect]) elif grid[newX][newY] ! = '*' : q.put([newX, newY, kLeft, currCoinCollect + int (grid[newX][newY])]) if (newX = = i2 and newY = = j2): visited[newX][newY][kLeft - int (grid[newX][newY] = = '*' )] = True # Incrementing the time taken # after every level time + = 1 # Return the total amount of time # taken to collect all the coin return coinCollect # Driver code if __name__ = = '__main__' : grid = [[ '*' , '0' , '1' , '2' ], [ '0' , '0' , '*' , '*' ], [ '*' , '*' , '6' , '8' ], [ '0' , '0' , '0' , '1' ]] i1, j1 = 0 , 2 i2, j2 = 3 , 3 K = 1 # Function call maxCoinCollected = collectAllCoin(grid, i1, j1, i2, j2, K) print (maxCoinCollected) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Function to find all the coin from the // grid in minimum number of time static int collectAllCoin( char [][] grid, int i1, int j1, int i2, int j2, int k1) { int m = grid.Length, n = grid[0].Length; // For storing the i, j index is // visited or not bool [, , ] visited = new bool [m, n, k1 + 1]; // For BFS Queue< int []> q = new Queue< int []>(); // <val, x, y> // Final coin collect to reach // destination in minimum time. int coinCollect = 8; // Pushing the current position q.Enqueue( new int [] { i1, j1, k1, grid[i1][j1] - '0' }); // Marking the current // position visited visited[i1, j1, k1] = true ; // Possible direction to move int [][] dir = { new int [] { 1, 0 }, new int [] { 0, 1 }, new int [] { -1, 0 }, new int [] { 0, -1 } }; // For counting the current // time while moving int time = 0; // Storing the minimum time to // reach at destination int minTime = int .MaxValue; while (q.Count > 0) { int size = q.Count; // This ensure that time has // reached greater than minimum // time to reach at destination if (time >= minTime) { break ; } for ( int i = 0; i < size; i++) { int [] curr = q.Dequeue(); int x = curr[0], y = curr[1], kLeft = curr[2], currCoinCollect = curr[3]; if (x == i2 && y == j2) { minTime = Math.Min(time, minTime); coinCollect = Math.Max(coinCollect, currCoinCollect); } // Explore all the direction for ( int k = 0; k < 4; k++) { int newX = 1; int newY = 1; if (newX >= 0 && newX < m && newY >= 0 && newY < n && visited[newX, newY, grid[newX][newY] == '*' ? kLeft - 1 : kLeft] == false ) { // Check if new cell is // obstacle and any k // move we have left to // cross this obstacle if (grid[newX][newY] == '*' && kLeft > 0) { q.Enqueue( new int [] { newX, newY, kLeft - 1, currCoinCollect }); } else if (grid[newX][newY] != '*' ) { q.Enqueue( new int [] { newX, newY, kLeft, currCoinCollect + (grid[newX][newY] - '0' ) }); } if (newX != i2 && newY != j2) visited[newX, newY, grid[newX][newY] == '*' ? kLeft - 1 : kLeft] = true ; } } } // Incrementing the time taken // after every level time++; } // Return the total amount of time // taken to collect all the coin return coinCollect; } // Driver code public static void Main() { char [][] grid = { new char [] { '*' , '0' , '1' , '2' }, new char [] { '0' , '0' , '*' , '*' }, new char [] { '*' , '*' , '6' , '8' }, new char [] { '0' , '0' , '0' , '1' } }; int i1 = 0, j1 = 2; int i2 = 3, j2 = 3; int K = 1; // Function call int maxCoinCollected = collectAllCoin(grid, i1, j1, i2, j2, K); Console.WriteLine(maxCoinCollected); } } |
Java
import java.util.*; public class GFG { static int collectAllCoin( char [][] grid, int i1, int j1, int i2, int j2, int k1) { int m = grid.length, n = grid[ 0 ].length; // For storing the i, j index is // visited or not boolean [][][] visited = new boolean [m][n][k1 + 1 ]; // For BFS Queue< int []> q = new LinkedList<>(); // <val, x, y> int coinCollect = 8 ; // Pushing the current position q.add( new int [] { i1, j1, k1, grid[i1][j1] - '0' }); visited[i1][j1][k1] = true ; // Possible direction to move int [][] dir = { { 1 , 0 }, { 0 , 1 }, { - 1 , 0 }, { 0 , - 1 } }; int time = 0 ; int minTime = Integer.MAX_VALUE; while (!q.isEmpty()) { int size = q.size(); // This ensure that time has // reached greater than minimum // time to reach at destination if (time >= minTime) { break ; } for ( int i = 0 ; i < size; i++) { int [] curr = q.poll(); int x = curr[ 0 ], y = curr[ 1 ], kLeft = curr[ 2 ], currCoinCollect = curr[ 3 ]; if (x == i2 && y == j2) { minTime = Math.min(time, minTime); coinCollect = Math.max(coinCollect, currCoinCollect); } // Explore all the directions for ( int k = 0 ; k < 4 ; k++) { int newX = x + dir[k][ 0 ]; int newY = y + dir[k][ 1 ]; if (newX >= 0 && newX < m && newY >= 0 && newY < n && visited[newX][newY] [grid[newX][newY] == '*' ? (kLeft > 0 ? kLeft - 1 : 0 ) : kLeft] == false ) { // Check if new cell is // obstacle and any k // move we have left to // cross this obstacle if (grid[newX][newY] == '*' && kLeft > 0 ) { q.add( new int [] { newX, newY, kLeft - 1 , currCoinCollect }); } else if (grid[newX][newY] != '*' ) { q.add( new int [] { newX, newY, kLeft, currCoinCollect + (grid[newX][newY] - '0' ) }); } if (newX != i2 || newY != j2) { visited[newX][newY] [grid[newX][newY] == '*' ? (kLeft > 0 ? kLeft - 1 : 0 ) : kLeft] = true ; } } } } // Incrementing the time taken // after every level time++; } // Return the total amount of time // taken to collect all the coin return coinCollect / 2 ; } // Driver code public static void main(String[] args) { char [][] grid = { { '*' , '0' , '1' , '2' }, { '0' , '0' , '*' , '*' }, { '*' , '*' , '6' , '8' }, { '0' , '0' , '0' , '1' } }; int i1 = 0 , j1 = 2 ; int i2 = 3 , j2 = 3 ; int K = 1 ; // Function call int maxCoinCollected = collectAllCoin(grid, i1, j1, i2, j2, K); System.out.println(maxCoinCollected); } } |
Javascript
// JavaScript code to implement the approach function collectAllCoin(grid, i1, j1, i2, j2, k) { const m = grid.length; const n = grid[0].length; // For storing the i, j index is // visited or not const visited = Array.from({length: m}, () => Array.from({length: n}, () => Array(k + 1).fill( false ))); // For BFS const q = []; // {x, y, k, coins} // Final coin collect to reach // destination in minimum time. let coinCollect = 0; // Pushing the current position q.push([i1, j1, k, Number(grid[i1][j1])]); // Marking the current // position visited visited[i1][j1][k] = true ; // Possible direction to move const dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]; // For counting the current // time while moving let time = 0; // Storing the minimum time to // reach at destination let minTime = Number.MAX_SAFE_INTEGER; while (q.length) { const size = q.length; // This ensure that time has // reached greater than minimum // time to reach at destination if (time >= minTime) { break ; } for (let i = 0; i < size; i++) { const curr = q.shift(); const [x, y, kLeft, currCoinCollect] = curr; if (x === i2 && y === j2) { minTime = Math.min(time, minTime); coinCollect = Math.max(coinCollect, currCoinCollect); } // Explore all the direction for (let d of dir) { const newX = x + d[0]; const newY = y + d[1]; if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY][kLeft - (grid[newX][newY] === '*' )]) { // Check if new cell is // obstacle and any k // move we have left to // cross this obstacle if (grid[newX][newY] === '*' && kLeft > 0) { q.push([newX, newY, kLeft - 1, currCoinCollect]); } else if (grid[newX][newY] !== '*' ) { q.push([newX, newY, kLeft, currCoinCollect + Number(grid[newX][newY])]); } if (newX === i2 && newY === j2) { visited[newX][newY][kLeft - (grid[newX][newY] === '*' )] = true ; } } } } // Incrementing the time taken // after every level time++; } // Return the total amount of time // taken to collect all the coin return coinCollect; } // Driver code const grid =[[ '' , '0' , '1' , '2' ], [ '0' , '0' , '' , '' ], [ '' , '' , '6' , '8' ], [ '0' , '0' , '0' , '1' ]]; const i1 = 0, j1 = 2, i2 = 3, j2 = 3, k = 1; const maxCoinCollected = collectAllCoin(grid, i1, j1, i2, j2, k); console.log(maxCoinCollected); |
8
Time Complexity: O(M * N)
Auxiliary Space: O(M * N)