一個二維陣列中所有島嶼之間的最大和是多少？必須使用遞回法

假設我們有一個N×M的網格，網格中的每個單元都包含一個值，這個值要么是0，要么是一個正整數。 一個島是一組在正交方向（北、東、南、西，但不是對角線方向）被0包圍的數值。 問題是要確定網格中所有島嶼之間的最大和。我們得到了一個叫做maxValueIsland的方法，它接收一個二維的ints陣列，并在網格中搜索島嶼。 一旦它找到一個島，它就會呼叫我們必須實作的getIslandValue方法。 然后maxValueIsland方法回傳所有島嶼值中的最大值。

我們已經獲得了幾個實用的方法來幫助生成和顯示2D網格。

public static void main（String[] args） {
    int map[][] = new int[5][5] 。

    int maxValue = 100。
    int dropChance =  25;
    randomIslands（map, maxValue, dropChance）。
    printIslands(map);
    System.out.println("有一個價值為" maxValueIsland(map)的島嶼。)
}

/********** Student Code Here **************************/

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  ) {
            if (map[r][c] != 0) {
                int value = getIslandValue（map, r, c）。
                if (value > maxValue) {
                    maxValue = value。
                }
            }
        }
    }
    return maxValue。
}

private static int getIslandValue（int map[][] 。int r, int c） {
  //這里是我們必須實施的方法。
    
}

/******************************************************************/

public static void randomIslands(int map[][], int maxPossibleValue, int chance)  {
    if (maxPossibleValue <= 0) {
        拋出 new IllegalArgumentException("最大可能值必須是一個正整數。")。
    }
    if (chance > 100 || chance < 0) {
        throw new IllegalArgumentException("掉錢的機會必須在0 <=p <=100")。
    }
    for (int r = 0; r < map.length; r  ) {
        for (int c = 0; c < map[r].length; c  ) {
            int possible = （int）（Math.random() * 100）。  1;
            if (possible <= chance) {
                map[r][c] = (int) (Math.random() * maxPossibleValue)   1;
            }
        }
    }
}

public static void printIslands(int island[][] ） {
    int maxDigits = getMaxDigits( island)。
    for (int r = 0; r < island.length; r  ) {
        for (int c = 0; c < island[r].length; c  ) {
            int value = island[r][c] 。
            String s = "%"/span>   maxDigits   "d";
            if (value != 0) {
                System.out.print(" |"/span>)。
                System.out.printf(s, value)。
                System.out.print("|")。
            } else {
                System.out.print(" ")。
                System.out.printf("%"/span>   maxDigits   "s"/span>, "-"/span>)。
                System.out.print(" ")。
            }
        }
        System.out.println(" ")。
    }
}

private static int getMaxDigits(int[] [] arr) {
    int maxDigitSize = 0;
    for (int r = 0; r < arr.length; r  ) {
        for (int c = 0; c < arr[r].length; c  ) {
            int value = arr[r][c] 。
            int digits = 0;
            while (value != 0) {
                digits  = 1;
                value /= 10;
            }
            if (digits > maxDigitSize) {
                maxDigitSize = digits。
            }
        }
    }
    return maxDigitSize;
}

我已經嘗試了幾次迭代，我知道我的基本情況是準確的。我在遞回呼叫方面遇到了麻煩。我需要考慮到在網格中向不同方向移動。(右、左、上、下)。以下是我所嘗試的：

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; // Base Case } int right = getIslandValue（map, r, c 1）。 int down = getIslandValue（map, r 1, c）。 int left = getIslandValue（map, r, c - 1）。 int up = getIslandValue（map, r - 1, c）; return map[r][c] (right left up down);

我得到了stackoverflow錯誤。我已經嘗試了許多不同的迭代。我最初的一個嘗試沒有產生堆疊溢位錯誤，但它沒有考慮到向左和向上移動：

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; // Base Case } int right = getIslandValue（map, r, c 1）。 int down = getIslandValue（map, r 1, c）。 return map[r][c] Math.max（right, down）。

最后，我知道我在訪問了一個島之后必須留下一個0的面包屑。我將不得不包括map[r][c] = 0;來完成這個任務。但這不是已經在我的基本案例的結尾處說明了嗎？map[r][c] == 0.....? ?

uj5u.com熱心網友回復：

最有效的方法是折疊陣列，但是遞回我想你想

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, 0}。
    {0, 0, 0, 0, 0}.
};

System.out.println("有一個價值為" maxValueIsland(map) "的島嶼。)

你得到

有一個島嶼的值是8。

標籤：

上一篇：如何洗掉安卓虛擬設備的發布版本，在安卓作業室？

下一篇：提取具有特殊字符的正則運算式