2D 정수 배열에서 최단 경로 찾기 Java

Question

나는 뱀이 2D int 배열을 지형으로 통과하는 뱀 게임을 만들고 있습니다. 2D 배열에 저장된 값은 교차하는 데 걸리는 시간 (초)을 나타냅니다.

int[][] MAP = { 
    { 1, 1, 1, 2, 2 }, 
    { 1, 2, 2, 2, 2 }, 
    { 3, 2, 2, 3, 1 }, 
    { 1, 1, 3, 2, 1 }, 
    { 1, 1, 3, 2, 1 } 
}; 

그래서 map[0][0]에서 map[0][4]에가는 예를 들어

는 1 + 1 + 2 + 2초 걸립니다. 뱀이 위치 map[startX][startY]에서 map[endX][endY]으로 이동할 수있는 최단 경로를 찾는 알고리즘을 어떻게 만들 수 있습니까?

이것은 숙제가 아니므로 나는 단지 재미있게 게임을 만들고있어이를 어떻게하는지 배우고 싶습니다.

Answer 1

이것은 "동적 프로그래밍"을 논의 할 때 다소 알려진 문제이며 심지어는 old post과 유사합니다.

하지만 난 그렇게, 또한 최단 경로를 인쇄하는 해결책을 찾을 수 없습니다 : 여기

public class FastestPathCalculator { 

    private final int[][] map; 

    public FastestPathCalculator(int[][] map) { 
     this.map=map; 
    } 

    public static void main(String[] args) { 
     int[][] map = new int[][]{ 
       {1, 1, 1, 4, 2}, 
       {1, 2, 5, 2, 2}, 
       {3, 2, 2, 3, 1}, 
       {1, 1, 3, 2, 1}, 
       {3, 1, 3, 2, 1} 
     }; 

     FastestPathCalculator c = new FastestPathCalculator(map); 
     boolean[] result = c.computeFastestPath(map); 
     c.printPath(result); 
    } 

는 부울 배열로 (0,0)에서 촬영 한 단계를 나타냅니다 (4,4) . TRUE 값은 오른쪽으로 단계가 있음을 의미하고, FALSE는 아래로 떨어짐을 의미합니다. 이 예제에서 배열에는 8 개의 셀이 있습니다.

public boolean[] computeFastestPath(int[][] map) { 
     int pathLength = map.length + map[0].length - 2; 
     boolean[] result = new boolean[pathLength]; 

     int[][] mapOfMinimalSums = buildMapOfMinimalSums(); 

     int x = map.length-1; 
     int y = map[0].length-1; 

     for (int i = pathLength - 1 ; i >= 0; i--) { 
      if (x == 0) 
       result[i] = true; 
      else if (y == 0) 
       result[i] = false; 
      else if (mapOfMinimalSums[x][y] == map[x][y] + mapOfMinimalSums[x][y-1]) { 
       result[i] = true; 
       y--; 
      } 
      else { 
       result[i] = false; 
       x--; 
      } 
     } 

     return result; 
    } 

    public void printPath(boolean[] result) { 
     String[][] newPath = new String[map.length][map[0].length]; 
     int x = 0; 
     int y = 0; 

     newPath[x][y] = String.valueOf(map[x][y]); 

     for (int i = 0 ; i < result.length; i++) { 
      if (result[i]) { 
       y++; 
      } else { 
       x++; 
      } 
      newPath[x][y] = String.valueOf(map[x][y]); 
     } 

     for (int i = 0 ; i < map.length; i++) { 
      for (int j = 0 ; j < map[0].length; j++) { 
       if (newPath[i][j] == null) { 
        System.out.print(" , "); 
       } else { 
        System.out.print(newPath[i][j] + ", "); 
       } 
      } 
      System.out.println(); 
     } 
     System.out.println(); 
    } 

    private int[][] buildMapOfMinimalSums() { 
     int[][] mapOfSums = new int[map.length][map[0].length]; 
     for (int i = 0 ; i < map.length; i++) { 
      for (int j = 0 ; j < map[0].length; j++) { 
       if (i == 0 && j == 0) 
        mapOfSums[i][j] = map[i][j]; 
       else if (i == 0) { 
        mapOfSums[i][j] = mapOfSums[i][j - 1] + map[i][j]; 
       } 
       else if (j == 0) 
        mapOfSums[i][j] = mapOfSums[i-1][j] + map[i][j]; 
       else 
        mapOfSums[i][j] = Math.min(mapOfSums[i-1][j], mapOfSums[i][j-1]) + map[i][j]; 
      } 
     } 
     return mapOfSums; 
    } 
}