NumberOfEnclaves.java

class NumEnclaves {
    public int numEnclaves(int[][] A) {
        if (A.length == 0) return 0;
        int N = A.length, M = A[0].length;
        for (int i=0; i<N; i++) {
            if (A[i][0] == 1) {
                dfs(A, i, 1);
            }
            if (A[i][M-1] == 1) {
                dfs(A, i, M-2);
            }
        }
        for (int i=0; i<M; i++) {
            if (A[0][i] == 1) {
                dfs(A, 1, i);
            }
            if (A[N-1][i] == 1) {
                dfs(A, N-2, i);
            }
        }

        int count = 0;
        for (int i=1; i<N-1; i++) {
            for (int j=1; j<M-1; j++) {
                if (A[i][j] == 1) count++;
            }
        }

        return count;
    }
    
    void dfs(int[][] A, int i, int j) {
        int N = A.length, M = A[0].length;
        if (A[i][j] != 1) return;
        A[i][j] = 0;
        if (i > 0 && A[i-1][j] == 1) { // top
            dfs(A, i-1, j);
        }
        if (j > 0 && A[i][j-1] == 1) { // left
            dfs(A, i, j-1);
        }
        if (i < N-1 && A[i+1][j] == 1) { // bottom
            dfs(A, i+1, j);
        }
        if (j < M-1 && A[i][j+1] == 1) { // right
            dfs(A, i, j+1);
        }
    }
}