Collect Max Points: A kids game has a board with an M*N matrix having M rows and N columns containing non-negative integer values as cell values. The kid can start from the first column of any row and can perform the following three navigations after collecting the points in that cell.
– He can move to the right cell.
– He can move to the top right cell.
– He can move to the bottom right cell.
The kid cannot come back to a previous column. He navigates until he reaches the last column of the matrix and collects the points in each cell. The program must print the maximum points a kid can collect for the given matrix while navigating.
Input Format:
The first line will contain the value of M and N separated by a space.
The next M lines will contain the values for N columns with the non-negative integer values separated by a space.
Output Format:
The integer value of the maximum points that can be collected.
Constraints:
2 <= M,N <= 30
Example Input/Output 1:
Input:
3 3
5 3 3
2 1 4
0 9 4
Output:
15
Explanation: The maximum points can be collected by navigating 2->9->4 and hence the sum is 2+9+4 = 15.
Example Input/Output 2:
Input:
4 4
1 3 1 5
2 2 4 1
5 0 2 3
0 6 1 2
Output:
16
Explanation: The maximum points 16 can be collected by navigating 5->6->2->3 or 5->2->4->5.
# Read dimensions of the matrix (M x N)
a, b = map(int, input().split())
# Initialize the matrix with its values
z = []
for _ in range(a):
z.append(list(map(int, input().split())))
# Dynamic programming loop to calculate maximum points
for j in range(1, b):
for i in range(a):
if i == 0:
# If at the top row, consider only moving right or diagonally down
z[i][j] += max(z[i][j - 1], z[i + 1][j - 1])
elif i == a - 1:
# If at the bottom row, consider only moving right or diagonally up
z[i][j] += max(z[i][j - 1], z[i - 1][j - 1])
else:
# For rows in the middle, consider all three possible movements
z[i][j] += max(z[i - 1][j - 1], z[i][j - 1], z[i + 1][j - 1])
# Find the maximum points collected by navigating through the last column
max_points = max(row[-1] for row in z)
# Print the maximum points
print(max_points)
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// Function to read a line of input
function readLine() {
return new Promise((resolve) => {
rl.question('', (input) => {
resolve(input);
});
});
}
// Main function to execute the program
async function main() {
// Read dimensions of the matrix (M x N)
const [numRows, numCols] = (await readLine()).split(' ').map(Number);
// Initialize the matrix with its values
const matrix = [];
for (let i = 0; i < numRows; i++) {
matrix.push((await readLine()).split(' ').map(Number));
}
// Dynamic programming loop to calculate maximum points
for (let col = 1; col < numCols; col++) {
for (let row = 0; row < numRows; row++) {
if (row === 0) {
// If at the top row, consider only moving right or diagonally down
matrix[row][col] += Math.max(matrix[row][col - 1], matrix[row + 1][col - 1]);
} else if (row === numRows - 1) {
// If at the bottom row, consider only moving right or diagonally up
matrix[row][col] += Math.max(matrix[row][col - 1], matrix[row - 1][col - 1]);
} else {
// For rows in the middle, consider all three possible movements
matrix[row][col] += Math.max(
matrix[row - 1][col - 1],
matrix[row][col - 1],
matrix[row + 1][col - 1]
);
}
}
}
// Find the maximum points collected by navigating through the last column
let maxPoints = matrix[0][numCols - 1];
for (let i = 1; i < numRows; i++) {
if (matrix[i][numCols - 1] > maxPoints) {
maxPoints = matrix[i][numCols - 1];
}
}
// Print the maximum points
console.log(maxPoints);
// Close the readline interface
rl.close();
}
// Call the main function to start the program
main();
using System;
namespace MaxPointsGame
{
class Program
{
static void Main(string[] args)
{
// Read dimensions of the matrix (M x N)
string[] dimensions = Console.ReadLine().Split();
int numRows = int.Parse(dimensions[0]);
int numCols = int.Parse(dimensions[1]);
// Initialize the matrix with its values
int[][] matrix = new int[numRows][];
for (int i = 0; i < numRows; i++)
{
matrix[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
}
// Dynamic programming loop to calculate maximum points
for (int col = 1; col < numCols; col++)
{
for (int row = 0; row < numRows; row++)
{
if (row == 0)
{
// If at the top row, consider only moving right or diagonally down
matrix[row][col] += Math.Max(matrix[row][col - 1], matrix[row + 1][col - 1]);
}
else if (row == numRows - 1)
{
// If at the bottom row, consider only moving right or diagonally up
matrix[row][col] += Math.Max(matrix[row][col - 1], matrix[row - 1][col - 1]);
}
else
{
// For rows in the middle, consider all three possible movements
matrix[row][col] += Math.Max(Math.Max(matrix[row - 1][col - 1], matrix[row][col - 1]), matrix[row + 1][col - 1]);
}
}
}
// Find the maximum points collected by navigating through the last column
int maxPoints = matrix[0][numCols - 1];
for (int i = 1; i < numRows; i++)
{
if (matrix[i][numCols - 1] > maxPoints)
{
maxPoints = matrix[i][numCols - 1];
}
}
// Print the maximum points
Console.WriteLine(maxPoints);
}
}
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// Read dimensions of the matrix (M x N)
int numRows, numCols;
cin >> numRows >> numCols;
// Initialize the matrix with its values
vector<vector<int>> matrix(numRows, vector<int>(numCols));
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
cin >> matrix[i][j];
}
}
// Dynamic programming loop to calculate maximum points
for (int col = 1; col < numCols; col++) {
for (int row = 0; row < numRows; row++) {
if (row == 0) {
// If at the top row, consider only moving right or diagonally down
matrix[row][col] += max(matrix[row][col - 1], matrix[row + 1][col - 1]);
} else if (row == numRows - 1) {
// If at the bottom row, consider only moving right or diagonally up
matrix[row][col] += max(matrix[row][col - 1], matrix[row - 1][col - 1]);
} else {
// For rows in the middle, consider all three possible movements
matrix[row][col] += max({matrix[row - 1][col - 1], matrix[row][col - 1], matrix[row + 1][col - 1]});
}
}
}
// Find the maximum points collected by navigating through the last column
int maxPoints = matrix[0][numCols - 1];
for (int i = 1; i < numRows; i++) {
if (matrix[i][numCols - 1] > maxPoints) {
maxPoints = matrix[i][numCols - 1];
}
}
// Print the maximum points
cout << maxPoints << endl;
return 0;
}
import java.util.Scanner;
public class MaxPointsGame {
public static void main(String[] args) {
// Read dimensions of the matrix (M x N)
Scanner scanner = new Scanner(System.in);
int numRows = scanner.nextInt();
int numCols = scanner.nextInt();
// Initialize the matrix with its values
int[][] matrix = new int[numRows][numCols];
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
matrix[i][j] = scanner.nextInt();
}
}
// Dynamic programming loop to calculate maximum points
for (int col = 1; col < numCols; col++) {
for (int row = 0; row < numRows; row++) {
if (row == 0) {
// If at the top row, consider only moving right or diagonally down
matrix[row][col] += Math.max(matrix[row][col - 1], matrix[row + 1][col - 1]);
} else if (row == numRows - 1) {
// If at the bottom row, consider only moving right or diagonally up
matrix[row][col] += Math.max(matrix[row][col - 1], matrix[row - 1][col - 1]);
} else {
// For rows in the middle, consider all three possible movements
matrix[row][col] += Math.max(Math.max(matrix[row - 1][col - 1], matrix[row][col - 1]), matrix[row + 1][col - 1]);
}
}
}
// Find the maximum points collected by navigating through the last column
int maxPoints = matrix[0][numCols - 1];
for (int i = 1; i < numRows; i++) {
if (matrix[i][numCols - 1] > maxPoints) {
maxPoints = matrix[i][numCols - 1];
}
}
// Print the maximum points
System.out.println(maxPoints);
}
}
