在2D整数数组Java中查找最短路径-Java 学习之路

我正在进行蛇形游戏，其中蛇穿过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] 的最短路径？

这不是一个家庭作业，我只是为了好玩而制作游戏，并想学习如何做到这一点 .

1 回答

在讨论"dynamic programming"时，这是一个有点已知的问题，甚至类似于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;
    }
}

回复于 2024-04-25T17:18:33+08:00

在2D整数数组Java中查找最短路径

1 回答

相关问题