Q4 PepCoding | Print All Paths With Maximum Gold

import java.io.*;
import java.util.*;

public class Main {

   private static class Pair {
      String psf;
      int i;
      int j;

      public Pair(String psf, int i, int j) {
         this.psf = psf;
         this.i = i;
         this.j = j;
      }
   }
   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int m = Integer.parseInt(br.readLine());
      int[][] arr = new int[n][m];

      for (int i = 0; i < n; i++) {
         String str = br.readLine();
         for (int j = 0; j < m; j++) {
            arr[i][j] = Integer.parseInt(str.split(" ")[j]);
         }
      }
        int max = Integer.MIN_VALUE;    //answer variable
        
      int dp[][] = new int[m][n];
      
      //filling last col
      for(int i = 0 ; i < m ; i++)
      dp[i][n-1] = arr[i][n-1];
      
      //now Traversing col wise from 2nd last col and finding minimum and also adding our own cost in it
      
        for(int j = n - 2 ; j >= 0 ; j--){
            
            for(int i = 0 ; i < m ;i++){
                
                //if first row
                if(i == 0 ){
                    dp[i][j] = Math.max(dp[i][j+1],dp[i+1][j+1]) + arr[i][j]; 
                    max = Math.max(max , dp[i][j]);
                }
                //if last row
                else if(i == m-1){
                    dp[i][j] = Math.max(dp[i][j+1],dp[i-1][j+1]) + arr[i][j];
                max = Math.max(max , dp[i][j]);
                }
                
                
                //rest of the matrix
                else{
                    dp[i][j] = Math.max(dp[i-1][j+1],Math.max(dp[i][j+1],dp[i+1][j+1])) + arr[i][j];
                
                max = Math.max(max , dp[i][j]);
                }
                
            }
        }
        
        System.out.println(max);
        // for(int i = 0 ; i < m ; i++){
        //     for(int j  = 0 ; j < n ; j++)
        //     System.out.print(dp[i][j] + " ");
            
        //     System.out.println();
        // }
        
        BFS(dp,max);
      
   }
   
   public static void BFS(int[][]dp,int maxcost){
       
       ArrayDeque<Pair> q = new ArrayDeque<>();
       
       //adding max element of first row and calling BFS
       for(int i = 0 ; i < dp.length ; i++)
       if(dp[i][0] == maxcost)
       q.add(new Pair(i+ "",i , 0));
       
       while(q.size()>0){
           
           Pair rem = q.removeFirst();
           int i = rem.i ; 
           int j = rem.j;
           
           //last col
           if(j == dp[0].length -1){
               System.out.println(rem.psf);
           }
           //first row
           else if(i == 0){
               int max = Math.max(dp[i][j+1],dp[i+1][j+1]);
               
               if(max == dp[i][j+1])
               q.add(new Pair(rem.psf + " d2",i , j+1));
               
               if(max == dp[i+1][j+1])
               q.add(new Pair(rem.psf +" d3" , i+1 , j+1));
           }
           
           //last row
           else if(rem.i == dp.length - 1){
               int max = Math.max(dp[i-1][j+1],dp[i][j+1]);
               
               if(max == dp[i-1][j+1])
               q.add(new Pair(rem.psf + " d1",i-1 , j+1));
               
               if(max == dp[i][j+1])
               q.add(new Pair(rem.psf + " d2",i , j+1));
           }
           
           //rest of the matrix
           else{
               int max = Math.max(dp[i-1][j+1],Math.max(dp[i][j+1],dp[i+1][j+1]));
               
               if(max == dp[i-1][j+1])
               q.add(new Pair(rem.psf + " d1",i-1 , j+1));
               
               if(max == dp[i][j+1])
               q.add(new Pair(rem.psf + " d2",i , j+1));
               
               if(max == dp[i+1][j+1])
               q.add(new Pair(rem.psf +" d3" , i+1 , j+1));
           }
       }
   }


}