Topic: Surrounded Regions

Following is an attempted solution to the problem listed at https://leetcode.com/problems/surrounde … scription/ .  Unfortunately, it fails with a java.lang.stackOverflowError on an example that has a matrix with about 40,000 cells.  It would seem that a non-recursive or a more efficient recursive solution might be required.

package surround;

public class surround {
    boolean check(char[][] arr, int i, int j, int nrows, int ncols){
        boolean surrounded = false;
        if (arr[i][j] == 'X') return true; // already X
        if (arr[i][j] == 'C') return true; // checking
        if (arr[i][j] == 'O'){
            arr[i][j] = 'C'; // checking
            if (i == 0 || j == 0 || i == (nrows-1) || j == (ncols-1)){
                arr[i][j] = 'O'; // connected to open border
                return false;
            }
            surrounded
                =  check(arr, i, j-1, nrows, ncols)
                && check(arr, i, j+1, nrows, ncols)
                && check(arr, i-1, j, nrows, ncols)
                && check(arr, i+1, j, nrows, ncols);
            if (surrounded) arr[i][j] = 'X';
            else arr[i][j] = 'O';
        }
        return surrounded;
    }
    boolean solve(char[][] board){
        boolean surrounded = true;
        int nrows = board.length;
        if (nrows == 0) return true;
        int ncols = board[0].length;
        for (int i = 1; i < nrows-1; i++){
            for (int j = 1; j < ncols-1; j++){
                surrounded &= check(board, i, j, nrows, ncols);
            }
        }
        return surrounded;
    }
    void printboard(char[][] board){
        int nrows = board.length;
        int ncols = board[0].length;
        for (int i = 0; i < nrows; i++){
            for (int j = 0; j < ncols; j++) System.out.print(board[i][j]);
            System.out.println("");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        char arr1[][]  = {{'X', 'X', 'X', 'X'},
                  {'X', 'O', 'O', 'X'},
                  {'X', 'X', 'O', 'X'},
                  {'X', 'O', 'X', 'X'}};
        char arr2[][]  = {{'O', 'X', 'O', 'X', 'O', 'O', 'X'},
                   {'O', 'X', 'X', 'O', 'X', 'O', 'X'},
                   {'X', 'O', 'O', 'O', 'X', 'X', 'X'},
                   {'X', 'X', 'X', 'X', 'O', 'X', 'O'}};
         surround sur1 = new surround();
         sur1.printboard(arr1);
        boolean surrounded = sur1.solve(arr1);
         sur1.printboard(arr1);
         System.out.println("All inner squares captured: " + surrounded + "\n");
         surround sur2 = new surround();
         sur2.printboard(arr2);
        surrounded = sur2.solve(arr2);
         sur2.printboard(arr2);
         System.out.println("All inner squares captured: " + surrounded + "\n");
    }
}

Following is the current output:

XXXX
XOOX
XXOX
XOXX

XXXX
XXXX
XXXX
XOXX

All inner squares captured: true

OXOXOOX
OXXOXOX
XOOOXXX
XXXXOXO

OXOXOOX
OXXXXOX
XXXXXXX
XXXXOXO

All inner squares captured: false