# What is wrong with this solution to the matrix path problem on Java – geeksforgeeks?

What is wrong with this solution to the matrix path problem on Java – geeksforgeeks? … here is a solution to the problem.

## What is wrong with this solution to the matrix path problem on Java – geeksforgeeks?

Can
you help me solve this geeksforgeeks problem
Given an N X N matrix matrix of positive integers Matrix[N][N]. There are only three possible walks for a cell Matrix[r][c].

1. Matrix [r+1][c].

2. Matrix [r+1][c-1].

3. Matrix [r+1

4. ][c+1].

Returns the maximum sum of all paths up to row N-1, starting from any column in row 0.

``````import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t  =1;
int n;
int a[][];
while(t-->0){
n = 17;
a = new int [n][n];
int input[]={ 67,280,171,381,930,781,925,4,393,380,246,433,762,258,5,166,315,503,385,728,854,350,464,288,304,80,689,56,313,843,92,379,122,614,111,403,394,387,406,138,767,651,571,880,260,927,398,926,429,782,653,634,132,468 ,274,435,548,314,490,212,156,933,942,629,546,404,31,292,142,436,781,260,86,703,140,697,630,537,622,410,318,275,44,801,94,669,236,993,982,77,204,137,10,497,765,907,900,147,550,42,582,331,301,19,33,792,715,14 ,680,336,424,350,962,467,150,408,135,737,400,468,814,956,956,175,452,72,433,704,218,983,97,799,665,749,169,49,541,883,63,572,570,486,921,884,304,423,291,790,159,42,257,324,997,212,498,801,283,283,504,500,617 ,952,650,281,700,818,329,592,52,743,164,621,228,436,856,883,858,498,672,17,540,928,340,536,139,190,336,773,472,191,272,88,142,921,720,842,90,400,433,141,143,948,114,722,384,969,605,593,819,276,961,358,556,301 ,893,46,842,581,819,665,771,90,104,265,363,823,106,452,574,890,945,68,190,58,790,925,378,746,517,196,373,478,905,280,130,798,326,323,730,144,987,500,585,90,764,947,264,221,751,837,463,47,257,652,456,46,576 ,185,143,444,381,867,921,285,147,402,434,472,724,163,615,710,15,551,151,130,498,414,703};
int k=0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
a[i][j] = input[k];
k++;
}
}
HashMap<String,Integer> h = new HashMap();
int max=Integer.MIN_VALUE,ans=0;
for(int i=0; i<a.length; i++){
ans=CostPath(a,0,i,h);
if(ans>max)
max=ans;
}
System.out.println(ans);
}

}

public static int CostPath(int a[][],int x,int y,HashMap<String,Integer>h){
if(h.containsKey(x+","+y))
return h.get(x+","+y);
int r;
if(x>=a.length || y>= a.length || x<0 || y<0 ){
r= Integer.MIN_VALUE;
}
else if(x==a.length-1 ){
r= a[x][y];
}

else{
r= a[x][y]+Math.max(Math.max(CostPath(a,x+1,y,h),CostPath(a,x+1,y-1,h)),CostPath(a,x+1,y-1,h));
}
h.put(x+","+y,r);
return r;
}
}
``````

This should give output 13785 but it gives 10689

### Solution

There are two small errors in the code:

``````r = a[x][y]+ Math.max(Math.max(CostPath(a,x+1,y,h),CostPath(a,x+1,y-1,h)),CostPath(a,x+1,y-1,h));
``````

is

wrong (`CostPath(a,x+1,y-1,h`) is calculated twice) should be:

``````r = a[x][y]+ Math.max(Math.max(CostPath(a,x+1,y,h),CostPath(a,x+1,y-1,h)),CostPath(a,x+1,y+1,h));
``````

And this

``````System.out.println(ans);
``````

Should be changed to

``````System.out.println(max);
``````

After making these two changes, the output is correct.
Side note:
There is no need to add invalid x,y values to the map path. Changes to prevent it and make the program more effective

``````r= Integer.MIN_VALUE;
``````

to

``````return 0;
``````