Блог

Предположим, у нас есть N x M сетка, в которой каждая ячейка сетки содержит значение, равное либо 0, либо положительному целому числу. Остров-это группа значений, окруженных 0 в ортогональных направлениях (север, восток, юг и запад, но не по диагонали). Проблема состоит в том, чтобы определить максимальную сумму между всеми островами в сетке. Нам дается вызываемый метод maxValueIsland , который берет 2D-массив int и сканирует сетку на наличие островов. Как только он находит остров, он вызывает метод 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("There is an island with a value of "   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) {
  //HERE IS THE METHOD WE MUST IMPLEMENT
    
}

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

public static void randomIslands(int map[][], int maxPossibleValue, int chance) {
    if (maxPossibleValue <= 0) {
        throw new IllegalArgumentException("The max possible value must be a positive integer.");
    }
    if (chance > 100 || chance < 0) {
        throw new IllegalArgumentException("The chance of money drop must be between 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 = "%"   maxDigits   "d";
            if (value != 0) {
                System.out.print(" |");
                System.out.printf(s, value);
                System.out.print("| ");
            } else {
                System.out.print("  ");
                System.out.printf("%"   maxDigits   "s", "-");
                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 …..??

Наиболее эффективный способ-это сворачивание массива, но рекурсивно, я полагаю, вы хотите

 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