Ошибка переполнения стека в функции самовызова в Java (количество островов)

Question

Я провел некоторое исследование причин ошибок переполнения стека и могу заключить, что это вызвано рекурсивной функцией в программе, которая должна «подсчитывать количество островков» в массиве. Я понимаю, что является причиной проблемы, но не уверен, почему это происходит, или мой главный вопрос - что на самом деле делать с этим. Я обнаружил, что если я замедляю программу тем, что она постоянно что-то печатает на консоль, это работает, но на это уходит вечность. Есть ли способ, которым я могу сохранить скорость программы без ошибок, или лучший способ решить проблему (найдите «количество островов», чтобы найти проблему). Кроме того, массив является двумерным с размером 1050 на 800.

public class NumOfIslands {
  static boolean[][] dotMap = new boolean[1050][800];
  static boolean visited[][] = new boolean[1050][800];
  static int total = 0;
  public static void main(String args[]) {
    defineArrays();
    run();
  }
  public static void findObjects(int xCord, int yCord) {
    for(int y = yCord - 1; y <= yCord + 1; y++) {
      for(int x = xCord - 1; x <= xCord + 1; x++) {
        if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
          if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
            visited[x][y] = true;
            findObjects(x,y);
            //System.out.println("test");
          }
        }
      }
    }
  }
  public static void defineArrays() {
    for(int y = 0; y < 800; y++) {
      for(int x = 0; x < 1050; x++) {
        dotMap[x][y] = true;
      }
    }
  }

  public static int run() {
    //dotMap = DisplayImage.isYellow;
    System.out.println(dotMap.length + " " + dotMap[0].length);
    int objects = 0;
    for(int y = 439; y < 560/*dotMap[0].length*/; y++) {
      for(int x = 70; x < 300/*dotMap.length*/; x++) {
        if(dotMap[x][y] == true && visited[x][y] != true) {
          visited[x][y] = true;
          objects++;
          findObjects(x,y);
        }
      }
    }
    System.out.println("total" + total);
    System.out.println(objects);
    return objects;

  }
}

Answer 1

проблема в этой функции

public static void findObjects(int xCord, int yCord) {


        for(int y = yCord - 1; y <= yCord + 1; y++) {
          for(int x = xCord - 1; x <= xCord + 1; x++) {
            if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
              if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
                visited[x][y] = true;
                 findObjects(x,y);
                //System.out.println("test");
              }
            }
          }
        }
      }`

здесь вы создаете стек рекурсивных вызовов для findobjects , и в конечном итоге он не имеет условия завершения, поэтому он заканчивается бесконечными стеками findobjects , так что мое решение, если вы просто проверяем, что если x и y varaibles не равны и посещение [x] [y] не соответствует истине, то нет необходимости вызывать рекурсию, просто закомментируйте рекурсивный вызов, потому что ваш цикл уже делает то, что вы хотите, чтобы рекурсивный вызов делаем.

 public static void findObjects(int xCord, int yCord) {


        for(int y = yCord - 1; y <= yCord + 1; y++) {
          for(int x = xCord - 1; x <= xCord + 1; x++) {
            if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
              if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
                visited[x][y] = true;
                //findObjects(x,y);
                //System.out.println("test");
              }
            }
          }
        }
      }

Answer 2

StackOverflowError причины . В вашем примере каждый вызов findObjects добавляет 2 переменные в стек int x и int y из циклов.

---

Одно из самых быстрых решений:

class Solution {
    int m, n;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int counter = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    visit(grid, i, j);
                    counter++;
                }
            }
        }
        return counter;
    }

    public void visit(char[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        visit(grid, i - 1, j);
        visit(grid, i + 1, j);
        visit(grid, i, j - 1);
        visit(grid, i, j + 1);
    }
}

---

Все рекурсивные алгоритмы могут быть реализованы с помощью циклов. Один из примеров ниже. В решении реализован алгоритм BFS (поиск в ширину), более подробную информацию о wikipedia .

class Solution {
  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;

    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          Queue<Integer> neighbors = new LinkedList<>();
          neighbors.add(r * nc + c);
          while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.add((row-1) * nc + col);
              grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.add((row+1) * nc + col);
              grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.add(row * nc + col-1);
              grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.add(row * nc + col+1);
              grid[row][col+1] = '0';
            }
          }
        }
      }
    }
    return num_islands;
  }
}