二维数组中所有岛之间的最大总和是多少？必须使用递归

Question

假设我们有一个N x M网格，其中网格的每个单元格都包含一个 0 或正整数的值。岛是在正交方向（北、东、南、西，但不是对角线）上由 0\xe2\x80\x99s 包围的一组值。问题是确定网格中所有岛屿之间的最大总和。我们得到了名为的方法maxValueIsland，该方法采用二维整数数组并扫描网格以查找岛屿。一旦它找到一个岛屿，它就会调用我们必须实现的 getIslandValue 方法。然后该方法maxValueIsland返回所有岛值中的最大值。

\n

我们提供了多种实用方法来帮助生成和显示 2D 网格。

\n

public static void main(String[] args) {\n    int map[][] = new int[5][5];\n\n    int maxValue = 100;\n    int dropChance = 25;\n    randomIslands(map, maxValue, dropChance);\n    printIslands(map);\n    System.out.println("There is an island with a value of " + maxValueIsland(map));\n}\n\n/********** Student Code Here **************************/\n\npublic static int maxValueIsland(int map[][]) {\n    int maxValue = 0;\n    for (int r = 0; r < map.length; r++) {\n        for (int c = 0; c < map[r].length; c++) {\n            if (map[r][c] != 0) {\n                int value = getIslandValue(map, r, c);\n                if (value > maxValue) {\n                    maxValue = value;\n                }\n            }\n        }\n    }\n    return maxValue;\n}\n\nprivate static int getIslandValue(int map[][], int r, int c) {\n  //HERE IS THE METHOD WE MUST IMPLEMENT\n    \n}\n\n/******************************************************************/\n\npublic static void randomIslands(int map[][], int maxPossibleValue, int chance) {\n    if (maxPossibleValue <= 0) {\n        throw new IllegalArgumentException("The max possible value must be a positive integer.");\n    }\n    if (chance > 100 || chance < 0) {\n        throw new IllegalArgumentException("The chance of money drop must be between 0 <= p <= 100");\n    }\n    for (int r = 0; r < map.length; r++) {\n        for (int c = 0; c < map[r].length; c++) {\n            int possible = (int) (Math.random() * 100) + 1;\n            if (possible <= chance) {\n                map[r][c] = (int) (Math.random() * maxPossibleValue) + 1;\n            }\n        }\n    }\n}\n\npublic static void printIslands(int island[][]) {\n    int maxDigits = getMaxDigits(island);\n    for (int r = 0; r < island.length; r++) {\n        for (int c = 0; c < island[r].length; c++) {\n            int value = island[r][c];\n            String s = "%" + maxDigits + "d";\n            if (value != 0) {\n                System.out.print(" |");\n                System.out.printf(s, value);\n                System.out.print("| ");\n            } else {\n                System.out.print("  ");\n                System.out.printf("%" + maxDigits + "s", "-");\n                System.out.print("  ");\n            }\n        }\n        System.out.println(" ");\n    }\n}\n\nprivate static int getMaxDigits(int[][] arr) {\n    int maxDigitSize = 0;\n    for (int r = 0; r < arr.length; r++) {\n        for (int c = 0; c < arr[r].length; c++) {\n            int value = arr[r][c];\n            int digits = 0;\n            while (value != 0) {\n                digits += 1;\n                value /= 10;\n            }\n            if (digits > maxDigitSize) {\n                maxDigitSize = digits;\n            }\n        }\n    }\n    return maxDigitSize;\n}\n

\n

我已经尝试了几次迭代，我知道我的基本情况是准确的。我在递归调用时遇到问题。我需要考虑网格中不同方向的行驶。（右、左、上、下）。这是我尝试过的：

\n

private static int getIslandValue(int map[][], int r, int c) {\n\n    if (r < 0 || c < 0 || r >= map.length || c >= map[r].length || map[r][c] == 0) {\n        return 0; // Base Case\n    }\n\n    int right = getIslandValue(map, r, c + 1);\n    int down = getIslandValue(map, r + 1, c);\n    int left = getIslandValue(map, r, c - 1);\n    int up = getIslandValue(map, r - 1, c);\n    \n    return map[r][c] + (right + left + up + down);\n}\n

\n

我遇到了 stackoverflow 错误。我尝试过许多不同的迭代。我最初的尝试之一没有产生任何 stackoverflow 错误，但它没有考虑向左和向上移动：

\n

private static int getIslandValue(int map[][], int r, int c) {\n\n    if (r < 0 || c < 0 || r >= map.length || c >= map[r].length || map[r][c] == 0) {\n        return 0; // Base Case\n    }\n\n    int right = getIslandValue(map, r, c + 1);\n    int down = getIslandValue(map, r + 1, c);\n    \n    return map[r][c] + Math.max(right, down);\n    \n}\n

\n

最后，我知道在访问一个岛屿后我必须留下 0 的面包屑。我必须包括map[r][c] = 0;才能实现这一点。但这不是已经在我的基本情况结束时考虑到了吗？map[r][c] == 0……？？

\n

Answer 1

最有效的方法是折叠数组，但递归地我想你想要

public static int maxValueIsland(int[][] map) {
    int maxValue = 0;
    for (int r = 0; r < map.length; r++)
        for (int c = 0; c < map[r].length; c++)
            maxValue = Math.max(maxValue, getIslandValue(map, r, c));
    return maxValue;
}

private static int getIslandValue(int[][] map, int r, int c) {
    if ( r < 0 || c < 0 || r >= map.length || c >= map[r].length || map[r][c] == 0)
        return 0;
    int h = map[r][c];
    map[r][c] = 0;
    return h + getIslandValue(map, r, c + 1) + getIslandValue(map, r, c - 1)
            + getIslandValue(map, r + 1, c) + getIslandValue(map, r - 1, c);
}

在哪里跑步

int[][] map = new int[][]{
    {0, 0, 1, 0, 0},
    {0, 1, 1, 0, 1},
    {1, 0, 0, 1, 1},
    {1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

System.out.println("There is an island with a value of " + maxValueIsland(map));

你得到

There is an island with a value of 8