Gold Mine Problem .txt

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
    
	 public static void main (String[] args) throws IOException
	 {
	 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	 StringBuffer sb=new StringBuffer();
	 int T=Integer.parseInt(br.readLine());
	 while(T-->0)
	 {
	     String[] s=br.readLine().split("\\s");
	     int m=Integer.parseInt(s[0]);
	     int n=Integer.parseInt(s[1]);
	     s=br.readLine().split("\\s");
	     int[][] arr=new int[m][n];
	     int[][] dp=new int[m+1][n+1];
	     int count=0;
	     for(int i=0;i<m;i++)
	     {
	         for(int j=0;j<n;j++)
	         {
	             arr[i][j]=Integer.parseInt(s[count++]);
	         }
	     }
	     for(int i=0;i<m+1;i++)
	     {
	         for(int j=0;j<n+1;j++)
	         {
	             dp[i][j]=-1;
	         }
	     }
	     int ans=0;
	     for(int i=0;i<m;i++)
	     {
	     ans=Math.max(ans,maxgold(arr,m,n,i,0,dp));
	     }
	     sb.append(ans+"\n");
	 }
	 System.out.print(sb);
	 }
	 public static int maxgold(int[][] arr,int m,int n,int posx,int posy,int[][] dp)
	 {
	     if(dp[posx][posy]!=-1)
	     {
	         return dp[posx][posy];
	     }
	     if(posy==n-1)
	     {
	         return dp[posx][posy]=arr[posx][posy];
	     }
	     
	     int smallans1,smallans2,smallans3;
	     smallans1=smallans2=smallans3=arr[posx][posy];
	     if(canplace(m,n,posx,posy+1))
	     {
	         smallans1+=maxgold(arr,m,n,posx,posy+1,dp);
	     }
	     if(canplace(m,n,posx-1,posy+1))
	     {
	         smallans2+=maxgold(arr,m,n,posx-1,posy+1,dp);
	     }
	     if(canplace(m,n,posx+1,posy+1))
	     {
	         smallans3+=maxgold(arr,m,n,posx+1,posy+1,dp);
	     }
	     return dp[posx][posy]=Math.max(smallans1,Math.max(smallans2,smallans3));
	 }
	 public static boolean canplace(int m,int n,int posx,int posy)
	 {
	     return posx>=0 && posy>=0 && posx<m && posy<n;
	 }
}