In this HackerRank Matrix Land problem solution, You are given a matrix A with n rows and m columns. Each cell contains some points. When a player passes a cell their score increases by the number written in that cell and the number in the cell becomes 0. (If the cell number is positive their score increases, otherwise it decreases.) The player starts from any cell in the first row and can move left, right, or down. The game is over when the player reaches the last row and stops moving. Print the maximum score that the player can get.
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static int matrixLand(int[][] grid) {
int m = grid[0].length;
int[][] dp = new int[grid.length][m];
int[] msl = new int[m];
int[] msr = new int[m];
int[] mslit = new int[m];
int[] msrit = new int[m];
for (int i = 0; i < grid.length; i++) {
Arrays.fill(msl, Math.max(grid[i][0], 0));
for (int j = 1; j < m; j++) {
msl[j] = Math.max(msl[j-1] + grid[i][j], 0);
}
Arrays.fill(msr, Math.max(grid[i][m-1], 0));
for (int j = 1; j < m; j++) {
msr[m-1-j] = Math.max(msr[m-j]+grid[i][m-1-j], 0);
}
Arrays.fill(mslit, grid[i][0]);
if (i > 0) {
mslit[0] += dp[i-1][0];
}
dp[i][0] = mslit[0]+msr[1];
for (int j = 1; j < m; j++) {
int top = i==0 ? 0 : dp[i-1][j];
mslit[j] = Math.max(mslit[j-1], top+msl[j-1])+grid[i][j];
int val = j+2>m ? 0 : msr[j+1];
dp[i][j] = mslit[j] + val;
}
Arrays.fill(msrit, grid[i][m-1]);
if (i > 0) {
msrit[m-1] += dp[i-1][m-1];
}
dp[i][m-1] = Math.max(dp[i][m-1], msrit[m-1]+msl[m-2]);
for (int j = 1; j < m; j++) {
int top = i==0 ? 0 : dp[i-1][m-1-j];
msrit[m-1-j] = Math.max(msrit[m-j], top+msr[m-j])+grid[i][m-1-j];
int val = j+2>m ? 0 : msl[m-1-j-1];
dp[i][m-1-j] = Math.max(dp[i][m-1-j], msrit[m-1-j] + val);
}
}
int result = dp[grid.length-1][0];
for (int j = 1; j < m; j++) {
result = Math.max(result, dp[grid.length-1][j]);
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
if (m==1) {
int result = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int item = Integer.parseInt(st.nextToken());
result += item;
}
bw.write(String.valueOf(result));
} else {
int[][] a = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int item = Integer.parseInt(st.nextToken());
a[i][j] = item;
}
}
int result = matrixLand(a);
bw.write(String.valueOf(result));
}
bw.newLine();
bw.close();
br.close();
}
}
Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int max_size = 500 + 5;
int n, m;
vector<vector<int>> A;
vector<int> pre;
vector<int> cur;
vector<int> l;
vector<int> r;
void get_cur(int idx) {
for (int i = 0, val = 0; i < m; i++) {
l[i] = val;
val += A[idx][i];
val = max(val, 0);
}
for (int i = m - 1, val = 0; i >= 0; i--) {
r[i] = val;
val += A[idx][i];
val = max(val, 0);
}
cur[0] = pre[0] + A[idx][0] + r[0];
int pre_max = pre[0];
for (int i = 1, sum = A[idx][0]; i < m; sum += A[idx][i], i++) {
int use_pre = pre_max + sum + A[idx][i] + r[i];
int use_cur = l[i] + pre[i] + A[idx][i] + r[i];
cur[i] = max(use_pre, use_cur);
pre_max = max(pre_max, pre[i] + l[i] - sum);
}
cur[m - 1] = max(cur[m - 1], pre[m - 1] + A[idx][m - 1] + l[m - 1]);
pre_max = pre[m - 1];
for (int i = m - 2, sum = A[idx][m - 1]; i >= 0; sum += A[idx][i], i--) {
int use_pre = pre_max + sum + A[idx][i] + l[i];
cur[i] = max(cur[i], use_pre);
pre_max = max(pre_max, pre[i] + r[i] - sum);
}
}
void solve() {
cin >> n >> m;
A = vector<vector<int>>(n , vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> A[i][j];
pre.resize(m);
cur.resize(m);
l.resize(m);
r.resize(m);
get_cur(0);
for (int i = 1; i < n; i++) {
swap(cur, pre);
get_cur(i);
}
int ans = INT_MIN;
for (int i = 0; i < m; i++)
ans = max(ans, cur[i]);
cout << ans << endl;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
int max(int x,int y);
int N,*table[4000000],*dp,*tdp,*left_sum,*right_sum,*dp_left_tree;
int main(){
int n,m,ma,total,i,j;
scanf("%d%d",&n,&m);
dp=(int*)malloc(m*sizeof(int));
tdp=(int*)malloc(m*sizeof(int));
left_sum=(int*)malloc(m*sizeof(int));
right_sum=(int*)malloc(m*sizeof(int));
dp_left_tree=(int*)malloc(m*sizeof(int));
for(i=0;i<n;i++)
table[i]=(int*)malloc(m*sizeof(int));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&table[i][j]);
for(i=0;i<n;i++){
for(j=total=0;j<m;j++){
if(j)
left_sum[j]=table[i][j]+left_sum[j-1];
else
left_sum[j]=table[i][j];
total+=table[i][j];
}
for(j=m-1;j>=0;j--)
if(j!=m-1)
right_sum[j]=table[i][j]+right_sum[j+1];
else
right_sum[j]=table[i][j];
for(j=m-2;j>=0;j--)
left_sum[j]=max(left_sum[j],left_sum[j+1]);
for(j=1;j<m;j++)
right_sum[j]=max(right_sum[j],right_sum[j-1]);
if(i){
for(j=0;j<m;j++)
dp_left_tree[j]=dp[j]+left_sum[j];
for(j=m-2;j>=0;j--)
dp_left_tree[j]=max(dp_left_tree[j],dp_left_tree[j+1]);
for(j=0;j<m;j++)
tdp[j]=right_sum[j]+dp_left_tree[j]-total;
for(j=0;j<m;j++)
dp_left_tree[j]=dp[j]+right_sum[j];
for(j=1;j<m;j++)
dp_left_tree[j]=max(dp_left_tree[j],dp_left_tree[j-1]);
for(j=0;j<m;j++){
if(left_sum[j]+dp_left_tree[j]-total>tdp[j])
tdp[j]=left_sum[j]+dp_left_tree[j]-total;
}
for(j=0;j<m;j++)
dp[j]=tdp[j];
}
else
for(j=0;j<m;j++)
dp[j]=left_sum[j]+right_sum[j]-total;
}
for(i=0,ma=-1000000001;i<m;i++)
if(dp[i]>ma)
ma=dp[i];
printf("%d",ma);
return 0;
}
int max(int x,int y){
return (x>y)?x:y;
}
0 Comments