Q3 PepCoding | Print All Paths With Minimum Cost

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 dp[][] = new int[m][n];
      
      //last cell
      dp[m-1][n-1] = arr[m-1][n-1];
      
      //last row
      for(int j = n-2 ; j >= 0 ; j--)
      dp[m-1][j] = dp[m-1][j+1] + arr[m-1][j];
      
      //last col
      for(int i = m-2 ; i >=0 ; i--)
      dp[i][n-1] = dp[i+1][n-1] + arr[i][n-1];
      
      //rest of the matrix
      for(int i = m -2 ; i >= 0 ;i--){
          for(int j = n-2 ; j >= 0 ;j--){
              
              dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j]) ;
              
              //adding your cell's cost
              dp[i][j] += arr[i][j];
          }
      }
      
        //answer stored in dp[0][0]
        System.out.println(dp[0][0]);
        
        //now we will use BFS to find all paths of minimum cost
        
        BFS(dp);
      
   }
   
   public static void BFS(int[][] dp){
       
       ArrayDeque<Pair> q = new ArrayDeque<>();
       q.add(new Pair("" , 0 , 0)); //adding first element
       
       while(q.size()>0){
          Pair rem = q.removeFirst();
          
          //if we have arrived at the last element
          if(rem.i ==dp.length-1 && rem.j == dp[0].length-1)
          System.out.println(rem.psf);
          
          //if last row we can move only right
          else if(rem.i == dp.length - 1)
          q.add(new Pair (rem.psf + "H", rem.i, rem.j+1));
          
          //if last col we can move only down
          else if(rem.j == dp[0].length - 1)
          q.add(new Pair(rem.psf + "V", rem.i+1, rem.j));
          
          //if we are in rest of the matrix
          else{
              
              //if horizontal element is smallest
              if(dp[rem.i][rem.j+1] < dp[rem.i+1][rem.j])
              q.add(new Pair (rem.psf + "H", rem.i, rem.j+1));
              
              //if vertical element is smallest
              else if(dp[rem.i+1][rem.j] < dp[rem.i][rem.j+1])
              q.add(new Pair(rem.psf + "V", rem.i+1, rem.j));
              
              //if both are equal
              else{
                q.add(new Pair(rem.psf + "V", rem.i+1, rem.j));
                q.add(new Pair (rem.psf + "H", rem.i, rem.j+1));
                
              }
          }
          
       }
   }

}