Как напечатать максимально допустимый путь в 2D массиве в Java?

Question

Я думаю, вы все знаете проблему «клубники», которую некоторые из вас дают вам на собеседовании, где вам нужно рассчитать путь между двумя углами 2D-массива, который можно перемещать только вверх или вправо, и вы можете вычислить максимально оцененный путь. У меня есть отлично работающий код, который делает это в Recursion, но его сложность - высокая. Я также решил проблему в решении «для петли», которая делает это в сложности O (n^2). , но в этом решении я просто не мог найти способ распечатать маршрут, как это было в рекурсивном решении. Это мой код (здесь довольно долго читать, поэтому я думаю, вы должны копировать, компилировать и запускать). взгляд на результаты решения рекурсии, BTW - Путь должен быть от левого нижнего угла к правому верхнему углу Я хочу, чтобы напечатать прокладывайте таким же образом, в лучшем решении:

public class Alg 
{ 
public static void main(String args[]) 
{ 
    String[] route = new String[100];     
    int[][]array = {{4,-2,3,6} 
        ,{9,10,-4,1} 
        ,{-1,2,1,4} 
        ,{0,3,7,-3}}; 
    String[][] route2 = new String[array.length][array[0].length];     
    int max = recursionAlg(array,array.length-1,0,route);   
    int max2 = loopAlg(array,array.length-1,0,route2); 
    System.out.println("The max food in the recursion solution is: "+max); 
    System.out.println("and the route is: "); 
    printRouteArray(route); 
    System.out.println("The max food in the loop solution: "+max2); 
    System.out.println("The route is: "); 
    //SHOULD PRINT HERE THE ROUTE 
} 


public static int loopAlg(int [][] arr,int x, int y, String[][] route) 
{ 
    int n=0; 
    int[][]count = new int[arr.length][arr[0].length]; 
    for(int i = x; i>=0 ; i--) 
    { 
     for(int j = 0; j<arr[0].length; j++) 
     { 
      if (i==x && j==0) {count[i][j]=arr[i][j];} 
      else if (i == x) { count[i][j]=count[i][j-1]+arr[i][j];} 
      else if (j == 0) { count[i][j]=count[i+1][j]+arr[i][j]; } 
      else{ 
       if (count[i][j-1]>count[i+1][j]) {count[i][j]=count[i][j-1]+arr[i][j];} 
       else { count[i][j]= count[i+1][j]+arr[i][j];} 
      } 
     } 
    } 
    return count[0][arr[0].length-1]; 
} 

public static int recursionAlg(int [][] arr, int x, int y,String[] route) 
{ 
    return recursionAlg(arr,0,x,y,arr[0].length-1,route,0);   
} 

public static int recursionAlg(int[][]arr,int count,int x, int y, int max_y, String[] route, int i) 
{ 
    if (x == 0 && y == max_y) {return count;} 
    else if (x == 0) { 
     route[i]="Right"; 
     return recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1); 
    } 
    else if (y==max_y){ 
     route[i]="Up"; 
     return recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1); 
    }  
    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)) 
    { 
     route[i]="Up"; 
     return recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1); 
    } 
    else 
    { 
     route[i]="Right"; 
     return recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1); 
    } 
} 

public static void printRouteArray(String[] arr) 
{ 
    int i=0; 
    while (i<arr.length && (arr[i]=="Up" || arr[i]=="Right")) 
    { 
     System.out.print(arr[i]+"-->"); 
     i++; 
    } 
    System.out.println("End"); 
}  
} 

Надеюсь, вы сможете помочь, спасибо!

Answer 1

Вам нужен еще один 2-мерный массив внутри loopAlg, который запоминает, какой шаг следует сделать для следующей записи для каждой записи в вашем исходном 2-мерном массиве. См. Следующий код и https://ideone.com/kM8BAZ для демонстрации:

public static void main(String args[]) 
{ 
    String[] route = new String[100];     
    int[][]array = {{4,-2,3,6} 
        ,{9,10,-4,1} 
        ,{-1,2,1,4} 
        ,{0,3,7,-3}}; 
    String[] route2 = new String[100];     
    int max = recursionAlg(array,array.length-1,0,route);   
    int max2 = loopAlg(array,array.length-1,0,route2); 
    System.out.println("The max food in the recursion solution is: "+max); 
    System.out.println("and the route is: "); 
    printRouteArray(route); 
    System.out.println("The max food in the loop solution: "+max2); 
    System.out.println("The route is: "); 
    printRouteArray(route2); 
} 

public enum Dirs {START, FROM_LEFT, FROM_DOWN}; 

public static int loopAlg(int [][] arr,int x, int y, String[] route) 
{ 

    int n=0; 
    int[][]count = new int[arr.length][arr[0].length]; 
    Dirs[][] directions = new Dirs[arr.length][arr[0].length]; 
    List<String> path = new ArrayList<String>(); 

    for(int i = x; i>=0 ; i--) 
    { 
     for(int j = 0; j<arr[0].length; j++) 
     { 
      if (i==x && j==0) {count[i][j]=arr[i][j]; directions[i][j] = Dirs.START;} 
      else if (i == x) { count[i][j]=count[i][j-1]+arr[i][j]; directions[i][j] = Dirs.FROM_LEFT;} 
      else if (j == 0) { count[i][j]=count[i+1][j]+arr[i][j]; directions[i][j] = Dirs.FROM_DOWN;} 
      else{ 
       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;} 
       else { count[i][j]= count[i+1][j]+arr[i][j];directions[i][j] = Dirs.FROM_DOWN;} 
      } 
     } 
    } 
    int i=0, j=arr[0].length-1; 
    while(directions[i][j]!= Dirs.START) { 
     if(directions[i][j] == Dirs.FROM_LEFT) { 
      path.add("Right"); 
      j--; 
     } 
     else { 
      path.add("Up"); 
      i++; 
     } 
    } 
    Collections.reverse(path); 
    i=0; 
    for(String part:path) { 
     route[i] = part; 
     i++; 
    } 

    return count[0][arr[0].length-1]; 
}