Количество ячеек земли, для которых мы не можем выйти за границу Сети.

Дана бинарная матричная сетка N x N , где 0 представляет морскую ячейку , а 1 представляет наземную ячейку . Движение состоит в переходе от одной ячейки земли к другой соседней (в 4-х направлениях, то есть влево, вправо, вверх и вниз) ячейке земли или выходе за границу сетки. Найдите количество ячеек земли в сетке, для которых мы не можем выйти за границу сетки за любое число ходов.

Примеры:

Input: grid[][] = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0},  {0, 0, 0, 0}}
Output: 3
Explanation: For the land cells at positions (1, 2), (2, 1) and (2, 2)
we cannot walk off the boundary.

Input:
grid [][]= {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
Output: 0

Подход: Задача может быть решена на основе следующей идеи:

First mark the land cells which are connected by the boundary and then count the total number of cells in the islands that are not marked.

Выполните следующие шаги, чтобы решить проблему:

• Возьмите посещенный массив размером N * N , каждый из которых инициализирован 0
• Выполните обход в глубину на каждой границе матрицы, т. е. первой строке, первом столбце, последней строке и последнем столбце.
  • Во время обхода проверяйте, есть ли какая-либо 1, которая присоединена к границе или нет.
  • Если она прикреплена, отметьте эту ячейку в посещенном массиве как 1 и продолжите поиск в глубину для соседних ячеек.
• Инициализируйте счетчик нулем и запустите цикл for для каждой ячейки данной матрицы и посещенной матрицы.
  • Если для какой-либо ячейки эта ячейка не посещается, а сетка содержит одну, то такая ячейка будет способствовать ответу и увеличивать счетчик на единицу.
• Распечатайте значение счетчика.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O (N * N), так как здесь мы используем DFS для ячеек матрицы и проходим по всей матрице.
Вспомогательное пространство: O(N * N) Посещенный массив той же размерности, что и у данной матрицы