Число замкнутых островов

Дана двухмерная матрица grid состоящая из  0 (земля) и 1 (вода).  Остров - это группа смежных 0, а замкнутый остров - это остров, окруженный (сверху, снизу, справа и слева) водой, то есть 1.

Вернуть количество завкнутых островов.

Пример 1:

Дано: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Результат: 2
Пояснение: 
Острова, помеченные серым цветом, замкнутые, потому что они окружены водой (единичками) сверху, снизу, слева и справа.

Пример 2:

Дано: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Результат: 1

Пример 3:

Дано: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
Результат: 2 (остров внутри острова) 

Ограничения:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

Идея решения 
Если мы возьмём любую ячейку нашей матрицы и если она окажется землей (значение 0), то нам нужно исследовать её соседей сверху, снизу слева и справа.

1. Если все соседи - вода (значение 1), то у нас остров, и мы можем увеличить счётчик островов.
2. Если хотя бы один сосед касается границы матрицы, то это не замкнутый остров. 
3. Если соседи не вода, но земля, то повторяем шаги 1 и 2 рекурсивно.

Таким образом, у нас получается обход вглубину (Depth First Search или сокращенно DFS).

Для того, чтобы не считать одну и ту же ячейку несколько раз (потому что она может оказаться соседом других 4 ячеек), нам нужно "перекрашивать" её в другое значение, например в 2.

Компилируемое решение

public int closedIsland(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;;
    int count = 0;

//  просматриваем все ящейки по столбцам и строкам, двойной цикл  for
    for (int row=0; row < n;row++) {
        for (int col=0;col<m;col++) {
// если ячейка земля и через поиск вглубину не касается стенок матрицы
// ни с какой стороны
            if (grid[row][col] == 0 && !dfs(row, col, grid)) {
                count++; // увеличиваем счётчик
            }
        }
    }
    return count;
}

 // та самая функция рекурсивной проверки, касаются ли соседи 
 // и их соседи границ матрицы: возвращает true если хотя бы один сосед
 // или его сосде, или сосед соседа и т.д. ... касается границы матрицы.
 // return true if cell touches the wall, 
 // or connected to another cell touching the wall
boolean dfs(int row, int col, int[][] grid) { 
    if (grid[row][col] == 0) {
        grid[row][col] = 2; // перекрашиваем просмотренную ячейку
    
        // текущая ячейка (земля) касается верхней границы ИЛИ
        // смотрим соседа сверху
        boolean up = row == 0 || dfs(row-1, col, grid);
        // текущая ячейка касается нижней границы ИЛИ
        // смотрим соседа снизу
        boolean down = row == grid.length-1 || dfs(row+1, col, grid);
        // текущая ячейка касается девой границы ИЛИ
        // смотрим соседа слева
        boolean left = col ==0 || dfs(row, col - 1, grid);
        // текущая ячейка касается правой границы ИЛИ
        // смотрим соседа справа
        boolean right = col == grid[0].length-1 || dfs(row, col + 1, grid);

        // если рекурсивно хотя бы один сосед касается границ матрицы, 
        // то возвращаем true, иначе возратим false
        return up || down || left || right;
    }
    // текущая ячейка вода, возвращаем false
    return false;
}

Сложность алгоритма
Поскольку нам нужно посмотреть все ячейки, которых количество nm, и на некоторые ячейки с водой мы заглядыаем несколько раз k=числу островов, с которыми эта вода граничит, и которых значительно меньше, чем nm, то k мы можем считать константой. И поэтому сложность алгоритма O(nm)