fork(1) download 
  1. import java.util.*;
  2. import java.lang.*;
  3.  
  4. class Main
  5. {
  6. 	public static void main(String args[])
  7. {
  8.     String[] route = new String[100];                  
  9.     int[][]array = {{4,-2,3,6}
  10.                     ,{9,10,-4,1}
  11.                     ,{-1,2,1,4}
  12.                     ,{0,3,7,-3}};
  13.     String[] route2 = new String[100];                
  14.     int max = recursionAlg(array,array.length-1,0,route);        
  15.     int max2 = loopAlg(array,array.length-1,0,route2);
  16.     System.out.println("The max food in the recursion solution is: "+max);
  17.     System.out.println("and the route is: ");
  18.     printRouteArray(route);
  19.     System.out.println("The max food in the loop solution: "+max2);
  20.     System.out.println("The route is: ");
  21.     printRouteArray(route2);
  22. }
  23.  
  24. public enum Dirs {START, FROM_LEFT, FROM_DOWN};
  25.  
  26. public static int loopAlg(int [][] arr,int x, int y, String[] route)
  27. {
  28.  
  29.     int n=0;
  30.     int[][]count = new int[arr.length][arr[0].length];
  31.     Dirs[][] directions = new Dirs[arr.length][arr[0].length];
  32.     List<String> path = new ArrayList<String>();
  33.  
  34.     for(int i = x; i>=0 ; i--)
  35.     {
  36.         for(int j = 0; j<arr[0].length; j++)
  37.         {
  38.             if (i==x && j==0) {count[i][j]=arr[i][j]; directions[i][j] = Dirs.START;}
  39.             else if (i == x) { count[i][j]=count[i][j-1]+arr[i][j]; directions[i][j] = Dirs.FROM_LEFT;}
  40.             else if (j == 0) { count[i][j]=count[i+1][j]+arr[i][j]; directions[i][j] = Dirs.FROM_DOWN;}
  41.             else{
  42.                 if (count[i][j-1]>count[i+1][j]) {count[i][j]=count[i][j-1]+arr[i][j];directions[i][j] = Dirs.FROM_LEFT;}
  43.                 else { count[i][j]= count[i+1][j]+arr[i][j];directions[i][j] = Dirs.FROM_DOWN;}
  44.             }
  45.         }
  46.     }
  47.     int i=0, j=arr[0].length-1;
  48.     while(directions[i][j]!= Dirs.START) {
  49.         if(directions[i][j] == Dirs.FROM_LEFT) {
  50.             path.add("Right");
  51.             j--;
  52.         }
  53.         else {
  54.             path.add("Up");
  55.             i++;
  56.         }
  57.     }
  58.     Collections.reverse(path);
  59.     i=0;
  60.     for(String part:path) {
  61.         route[i] = part;
  62.         i++;
  63.     }
  64.  
  65.     return count[0][arr[0].length-1];
  66. }   
  67.  
  68. public static int recursionAlg(int [][] arr, int x, int y,String[] route)
  69. {
  70.     return recursionAlg(arr,0,x,y,arr[0].length-1,route,0);        
  71. }
  72.  
  73. public static int recursionAlg(int[][]arr,int count,int x, int y, int max_y, String[] route, int i)
  74. {
  75.     if (x == 0 && y == max_y) {return count;}
  76.     else if (x == 0) {
  77.         route[i]="Right";
  78.         return recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1);
  79.     }
  80.     else if (y==max_y){
  81.         route[i]="Up";
  82.         return recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1);
  83.     }     
  84.     else if (recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1)>recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1))
  85.     {
  86.         route[i]="Up";
  87.         return  recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1);
  88.     }
  89.     else
  90.     {
  91.         route[i]="Right";
  92.         return recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1);
  93.     }
  94. }
  95.  
  96. public static void printRouteArray(String[] arr)
  97. {
  98.     int i=0;
  99.     while (i<arr.length && arr[i]!=null)
  100.     {
  101.         System.out.print(arr[i]+"-->");
  102.         i++;
  103.     }
  104.     System.out.println("End");
  105. }    
  106. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
The max food in the recursion solution is: 25
and the route is: 
Up-->Up-->Right-->Up-->Right-->Right-->End
The max food in the loop solution: 25
The route is: 
Up-->Up-->Right-->Up-->Right-->Right-->End
https://ideone.com/kM8BAZ
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!