Problem description.
Impressed with Agnes' jumping skills, Gru has decided to build a new game for her. Gru has laid out a grid of N x M tiles, and each tiles contains some (positive) number of candies. The rules of the games are as following: - Agnes starts from the tile (0, 0) // 0 based index - She has to reach the tile (N-1, M-1) - At a time she can either move in +x direction by 1 tile or in +y direction.. - She cannot go left or up . - She can go from (0, 0) -> (N-1, M-1) only once. See example below for the movement for more clarity Now Agnes wants to collect maximum number of candies possible while playing the game. Can you help her out? Example: Consider the matrix of 4x3, she starts at (0,0) and collects all candies from (0, 0). Now she can move to (0, 1) or (1, 0). More generically, allowed moves from (i, j) are - (i+1, j) OR - (i, j+1) Illegal moves - (i-1, j) - (i, j-1)
Input
First line contains number of tests - T. Each test consists of following lines: First line contains two space separated positive integers N and M, representing the grid size Next N lines represents rows of the grid . Each of the N lines contains M integers.
Output
Output a single integer that is equal to maximum candies that Agnes can collect.
Constraints
0 < T < 10 0 < N < 1000 0 < M < 1000
Example
Input
1 2 4 1 2 3 8 3 4 5 6
Output
20
Explanation
Example case 1.
N = 2, M = 4 First row a[0][0] = 1 a[0][1] = 2 a[0][2] = 3 a[0][3] = 8 Second row a[1][0] = 3 a[1][1] = 4 a[1][2] = 5 a[1][3] = 6 Objective reach from a[0][0] -> a[1][3] Take the path: a[0][0] -> a[0][1] -> a[0][2] -> a[0][3]-> a[1][3] Answer = 1 + 2 + 3 + 8 + 6 = 20
Maximum Candies CodeChef Solution in JAVA
import java.io.*;
import java.util.*;
class MaximizingCandies {
public static long dp[][];
public static void main(String argsp[]) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t-- > 0) {
int n = in.nextInt();
int m = in.nextInt();
long arr[][] = new long[n][m];
dp = new long[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = in.nextInt();
dp[i][j] = Long.MIN_VALUE;
}
}
dp[n - 1][m - 1] = arr[n - 1][m - 1];
long answer = solve(arr, 0, 0);
System.out.println(answer);
}
in.close();
}
public static long solve(long arr[][], int x, int y) {
if (dp[x][y] > Integer.MIN_VALUE) return dp[x][y];
int n = arr.length;
int m = arr[0].length;
if (x == n - 1) {
dp[x][y] = arr[x][y] + solve(arr, x, y + 1);
} else if (y == m - 1) {
dp[x][y] = arr[x][y] + solve(arr, x + 1, y);
} else {
dp[x][y] = arr[x][y] + Math.max(solve(arr, x, y + 1), solve(arr, x + 1, y));
}
return dp[x][y];
}
}
Maximum Candies CodeChef Solution in CPP
//I_F_A
#include "bits/stdc++.h"
using namespace std;
#define N 1001
long long dp[N][N];
long long arr[N][N];
long long n,m;
long long solve(long long i,long long j){
if(i == n && j == m){
return arr[i][j];
}
if(dp[i][j] == INT_MAX){
long long ans1 = arr[i][j] , ans2 = arr[i][j];
if(i + 1 <= n){
ans1 = ans1 + solve(i+1,j);
}
if(j + 1 <= m){
ans2 = ans2 +solve(i,j+1);
}
dp[i][j] = max(ans1,ans2);
}
return dp[i][j];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while(tc--){
cin >> n >> m;
for(long long i=1;i<=n;i++){
for(long long j=1;j<=m;j++){
cin >> arr[i][j];
dp[i][j] = INT_MAX;
}
}
cout << solve(1,1) << endl;
}
}Maximum Candies -CodeChef Solution in Python
from sys import stdin
def maxCost(cost, m, n):
tc = [[0 for x in range(C)] for x in range(R)]
tc[0][0] = cost[0][0]
for i in range(1, m + 1):
tc[i][0] = tc[i - 1][0] + cost[i][0]
for j in range(1, n + 1):
tc[0][j] = tc[0][j - 1] + cost[0][j]
for i in range(1, m + 1):
for j in range(1, n + 1):
tc[i][j] = max(tc[i - 1][j - 1], tc[i - 1][j], tc[i][j - 1]) + cost[i][j]
return tc[m][n]
for _ in range(int(stdin.readline())):
R,C = map(int,stdin.readline().split())
cost =[]
for i in range(R):
cost.append(list(map(int,stdin.readline().split())))
print(maxCost(cost,R-1,C-1))
Disclaimer: The above Problem (Maximum Candies) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
