PROBLEM LINK:
Author: Chandan Boruah
Tester: Harsh Raj
Editorialist: Chandan Boruah
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP or Graph Theory.
PROBLEM:
Given a 2D array and you start from top row to reach the bottom row, you can start anywhere in the first row and end anywhere in the bottom row. You can go straight down or diagonally left or right. Each cell in the grid has a weight/points. Your point is equal to the sum of all the points collected, print the maximum sum that you can get.
QUICK EXPLANATION/EXPLANATION:
Setter: Find all the grid positions that aren’t empty and find all the grid positions that are mutually reachable. Run a graph traversal such that you traverse downwards, and find the maximum sum possible.
Tester: Do a dynamic recursive algorithm to recursively go downwards, diagonally left or diagonally right.
SOLUTIONS:
chandubaba's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
string[]ss=Console.ReadLine().Split();
int x=int.Parse(ss[0]);
int y=int.Parse(ss[1]);
int[,]arr=new int[x,y];
for(int i=0;i<x;i++)
{
string s=Console.ReadLine();
for(int j=0;j<y;j++)
{
arr[i,j]=int.Parse(s[j]+"");
}
}
int k=0;
List<string>ll=new List<string>();
List<int>val=new List<int>();
for(int i=0;i<x;i++)
{
for(int j=0;j<y;j++)
{
if(arr[i,j]!=0)
{
ll.Add(i+" "+j);
val.Add(arr[i,j]);
}
}
}
int[,]path=new int[ll.Count,ll.Count];
for(int i=0;i<ll.Count;i++)
{
string[]st=ll[i].Split();
int xi=int.Parse(st[0]);
int yi=int.Parse(st[1]);
for(int j=0;j<ll.Count;j++)
{
if(i==j)continue;
st=ll[j].Split();
int xj=int.Parse(st[0]);
int yj=int.Parse(st[1]);
if(xj<=xi)continue;
int disti=xj-xi;
int distj=Math.Abs(yj-yi);
if(distj<=disti)
{
path[i,j]=1;
}
}
}
int max=0;
for(int i=0;i<ll.Count;i++)
{
Stack<int>st=new Stack<int>();
Stack<int>vst=new Stack<int>();
st.Push(i);
vst.Push(val[i]);
int c=0;
while(st.Count>0)
{
int q=st.Pop();
int now=vst.Pop();
c=Math.Max(now,c);
for(int j=0;j<ll.Count;j++)
{
if(path[q,j]==1)
{
st.Push(j);
vst.Push(now+val[j]);
}
}
}
max=Math.Max(c,max);
}
Console.WriteLine(max);
}
}
harshra22's Solution
// simple dp based solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int N = 52;
int arr[N][N],dp[N][N],x,y;
int solve(int i,int j){
if(i<=0 || j<=0)
return 0;
else if(i>x || j>y)
return 0;
else if(dp[i][j] != -1)
return dp[i][j];
dp[i][j] = arr[i][j] + max({solve(i+1,j),solve(i+1,j-1),solve(i+1,j+1)});
return dp[i][j];
}
int main(){
cin >> x >> y;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
arr[i][j] = 0;
dp[i][j] = -1;
}
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
char ch; cin >> ch;
arr[i][j] = ch-'0';
}
}
int ans = 0;
for(int j=1;j<=y;j++)
ans = max(ans,solve(1,j));
cout << ans << '\n';
return 0;
}