Optimal cell in matrix to collect maximum coins
Given an M * N matrix matrix[][], where each cell is either an obstacle β#β, a coin βCβ, or empty β0β, the task is to choose one empty cell optimally to maximize the coins collected. You can collect coins from the same row and column where you stand until there are no obstacles.
Note: We can only start from the empty cells, that is where matrix[i][j] = 0.
Examples:
Input: matrix = {
{β0β, βCβ, β0β, β0β},
{βCβ, β0β, β#β, βCβ},
{β0β, βCβ, β0β, β0β}}
Output: 3
Explanation: If we start at empty cell matrix[1][1], then we can collect 2 coins by traversing the column and 1 coin by traversing the row.Input: matrix = {
{βCβ, β#β, βCβ, β0β},
{βCβ, βC, β#β, β0β},
{β#β, β#β, β#β, β0β}}
Output: 1
Explanation: If we start at empty cell matrix[0][2], then we can collect 0 coins by traversing the column and 1 coin by traversing the row.
Approach: To solve the problem, follow the below idea:
Keep cumulative sum or prefix sum (dp) for each row from left to right, we encounter βCβ weβll increase our coinCount by 1, if we get β#β the reset out cointCount to 0. Similar, weβll do for same row from right to left.
Again, for each column, traverse from top to bottom, if we encounter βCβ weβll increase our coinCount by 1, if we get β#β the reset out cointCount to 0. Similar, weβll do for same row from bottom to top.
Now, Iterate again on each empty cell and maximise our coin from cumulative (dp).
Step-by-step algorithm:
- Create a 2D vector dp[][] to store cumulative coins in each cell.
- Iterate through each row, moving left to right, and calculate cumulative coins for each cell based on the presence of coins (βCβ) and obstacles (β#β).
- Repeat the process, moving right to left within each row, updating cumulative coins in the cells.
- Iterate through each column, moving top to bottom, and calculate cumulative coins for each cell based on the presence of coins and obstacles.
- Repeat the process, moving bottom to top within each column, updating cumulative coins in the cells.
- Find the maximum number of coins in an empty cell by considering the cumulative coins from both row and column movements.
- Output the maximum collected coins.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number of coins that can be
// collected.
int maxCollectedCoins(vector<vector<char> >& matrix)
{
// Get the number of rows and columns in the matrix
int rows = matrix.size();
int cols = matrix[0].size();
// 2D vector to store cumulative coins in each cell
vector<vector<int> > dp(rows, vector<int>(cols, 0));
// Calculate cumulative coins for each cell in the row
for (int i = 0; i < rows; ++i) {
int coinCount = 0;
// Iterate from left to right in the row
for (int j = 0; j < cols; ++j) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
// Increment coinCount if a coin is found
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from right to left in the row
for (int j = cols - 1; j >= 0; --j) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Calculate cumulative coins for each cell in the
// column
for (int j = 0; j < cols; ++j) {
int coinCount = 0;
// Iterate from top to bottom in the column
for (int i = 0; i < rows; ++i) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// // Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from bottom to top in the column
for (int i = rows - 1; i >= 0; --i) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Find the maximum number of coins in an empty cell
int maxCoins = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '0') {
maxCoins = max(
maxCoins,
dp[i][j]); // Update maxCoins if larger
// value is found
}
}
}
return maxCoins;
}
int main()
{
// Create a vector representing the matrix
vector<vector<char> > matrix
= { { '0', 'C', '0', '0' },
{ 'C', '0', '#', 'C' },
{ '0', 'C', '0', '0' } };
// Call the maxCollectedCoins function with the provided
// matrix
int result = maxCollectedCoins(matrix);
// Output the result
cout << "Max Collected Coins: " << result << endl;
return 0;
}
import java.util.Arrays;
public class MaxCollectedCoins {
// Function to find the maximum number of coins that can be collected.
static int maxCollectedCoins(char[][] matrix) {
// Get the number of rows and columns in the matrix
int rows = matrix.length;
int cols = matrix[0].length;
// 2D array to store cumulative coins in each cell
int[][] dp = new int[rows][cols];
// Calculate cumulative coins for each cell in the row
for (int i = 0; i < rows; ++i) {
int coinCount = 0;
// Iterate from left to right in the row
for (int j = 0; j < cols; ++j) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from right to left in the row
for (int j = cols - 1; j >= 0; --j) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Calculate cumulative coins for each cell in the column
for (int j = 0; j < cols; ++j) {
int coinCount = 0;
// Iterate from top to bottom in the column
for (int i = 0; i < rows; ++i) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from bottom to top in the column
for (int i = rows - 1; i >= 0; --i) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Find the maximum number of coins in an empty cell
int maxCoins = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '0') {
maxCoins = Math.max(maxCoins, dp[i][j]); // Update maxCoins if larger value is found
}
}
}
return maxCoins;
}
public static void main(String[] args) {
// Create a 2D array representing the matrix
char[][] matrix = {
{ '0', 'C', '0', '0' },
{ 'C', '0', '#', 'C' },
{ '0', 'C', '0', '0' }
};
// Call the maxCollectedCoins function with the provided matrix
int result = maxCollectedCoins(matrix);
// Output the result
System.out.println("Max Collected Coins: " + result);
}
}
// This code is contributed by akshitaguprzj3
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum number of coins that can be
// collected.
static int MaxCollectedCoins(List<List<char>> matrix)
{
// Get the number of rows and columns in the matrix
int rows = matrix.Count;
int cols = matrix[0].Count;
// 2D list to store cumulative coins in each cell
List<List<int>> dp = new List<List<int>>(rows);
for (int i = 0; i < rows; ++i)
{
dp.Add(new List<int>(cols));
for (int j = 0; j < cols; ++j)
{
dp[i].Add(0);
}
}
// Calculate cumulative coins for each cell in the row
for (int i = 0; i < rows; ++i)
{
int coinCount = 0;
// Iterate from left to right in the row
for (int j = 0; j < cols; ++j)
{
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#')
{
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C')
{
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from right to left in the row
for (int j = cols - 1; j >= 0; --j)
{
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#')
{
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C')
{
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Calculate cumulative coins for each cell in the column
for (int j = 0; j < cols; ++j)
{
int coinCount = 0;
// Iterate from top to bottom in the column
for (int i = 0; i < rows; ++i)
{
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#')
{
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C')
{
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from bottom to top in the column
for (int i = rows - 1; i >= 0; --i)
{
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] == '#')
{
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] == 'C')
{
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Find the maximum number of coins in an empty cell
int maxCoins = 0;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (matrix[i][j] == '0')
{
maxCoins = Math.Max(maxCoins, dp[i][j]); // Update maxCoins if larger
// value is found
}
}
}
return maxCoins;
}
static void Main()
{
// Create a list representing the matrix
List<List<char>> matrix = new List<List<char>>
{
new List<char> { '0', 'C', '0', '0' },
new List<char> { 'C', '0', '#', 'C' },
new List<char> { '0', 'C', '0', '0' }
};
// Call the MaxCollectedCoins function with the provided
// matrix
int result = MaxCollectedCoins(matrix);
// Output the result
Console.WriteLine("Max Collected Coins: " + result);
}
}
// Function to find the maximum number of coins that can be collected.
function maxCollectedCoins(matrix) {
// Get the number of rows and columns in the matrix
let rows = matrix.length;
let cols = matrix[0].length;
// 2D array to store cumulative coins in each cell
let dp = Array.from(Array(rows), () => Array(cols).fill(0));
// Calculate cumulative coins for each cell in the row
for (let i = 0; i < rows; ++i) {
let coinCount = 0;
// Iterate from left to right in the row
for (let j = 0; j < cols; ++j) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] === '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] === 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from right to left in the row
for (let j = cols - 1; j >= 0; --j) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] === '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] === 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Calculate cumulative coins for each cell in the column
for (let j = 0; j < cols; ++j) {
let coinCount = 0;
// Iterate from top to bottom in the column
for (let i = 0; i < rows; ++i) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] === '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] === 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
// Reset coinCount for the reverse iteration
coinCount = 0;
// Iterate from bottom to top in the column
for (let i = rows - 1; i >= 0; --i) {
// Reset coinCount if an obstacle is encountered
if (matrix[i][j] === '#') {
coinCount = 0;
}
// Increment coinCount if a coin is found
else if (matrix[i][j] === 'C') {
++coinCount;
}
// Update cumulative coins for the cell
dp[i][j] += coinCount;
}
}
// Find the maximum number of coins in an empty cell
let maxCoins = 0;
for (let i = 0; i < rows; ++i) {
for (let j = 0; j < cols; ++j) {
if (matrix[i][j] === '0') {
maxCoins = Math.max(maxCoins, dp[i][j]); // Update maxCoins if larger value is found
}
}
}
return maxCoins;
}
// Main function
function main() {
// Create a matrix representing the grid
let matrix = [
['0', 'C', '0', '0'],
['C', '0', '#', 'C'],
['0', 'C', '0', '0']
];
// Call the maxCollectedCoins function with the provided matrix
let result = maxCollectedCoins(matrix);
// Output the result
console.log("Max Collected Coins:", result);
}
// Call the main function
main();
def max_collected_coins(matrix):
rows = len(matrix)
cols = len(matrix[0])
# 2D list to store cumulative coins in each cell
dp = [[0 for _ in range(cols)] for _ in range(rows)]
# Calculate cumulative coins for each cell in the row
for i in range(rows):
coin_count = 0
# Iterate from left to right in the row
for j in range(cols):
if matrix[i][j] == '#':
coin_count = 0
elif matrix[i][j] == 'C':
coin_count += 1
dp[i][j] += coin_count
# Reset coin_count for the reverse iteration
coin_count = 0
# Iterate from right to left in the row
for j in range(cols-1, -1, -1):
if matrix[i][j] == '#':
coin_count = 0
elif matrix[i][j] == 'C':
coin_count += 1
dp[i][j] += coin_count
# Calculate cumulative coins for each cell in the column
for j in range(cols):
coin_count = 0
# Iterate from top to bottom in the column
for i in range(rows):
if matrix[i][j] == '#':
coin_count = 0
elif matrix[i][j] == 'C':
coin_count += 1
dp[i][j] += coin_count
# Reset coin_count for the reverse iteration
coin_count = 0
# Iterate from bottom to top in the column
for i in range(rows-1, -1, -1):
if matrix[i][j] == '#':
coin_count = 0
elif matrix[i][j] == 'C':
coin_count += 1
dp[i][j] += coin_count
# Find the maximum number of coins in an empty cell
max_coins = 0
for i in range(rows):
for j in range(cols):
if matrix[i][j] == '0':
max_coins = max(max_coins, dp[i][j])
return max_coins
# Main function to test the code
if __name__ == "__main__":
matrix = [
['0', 'C', '0', '0'],
['C', '0', '#', 'C'],
['0', 'C', '0', '0'],
]
result = max_collected_coins(matrix)
print("Max Collected Coins:", result)
Output
Max Collected Coins: 3
Time Complexity: O(M * N), where M is the number of rows and N is the number of columns.
Auxiliary Space: O(M * N)
Contact Us