在2D整數數組中尋找最短路徑Java

Question

我正在製作一款蛇遊戲，其中蛇穿過2D int數組作爲其地形。存儲在二維數組中的值表示以秒爲單位的時間跨越。

例如，

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; 
    } 
}