Задача: 1020. Number of Enclaves
Сложность: medium

Вам дана двоичная матричная сетка m 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

👨‍💻 Алгоритм:

1⃣Обработка граничных сухопутных ячеек:
Пройдитесь по всем ячейкам, которые находятся на границе сетки (первый и последний ряды, первый и последний столбцы). Если ячейка содержит 1, начните поиск в глубину (DFS) или поиск в ширину (BFS), чтобы пометить все достижимые из нее сухопутные ячейки как посещенные.

2⃣Проверка всех ячеек:
Пройдите по всем ячейкам матрицы, считая количество сухопутных ячеек, которые не были посещены в предыдущем шаге.

3⃣Возврат результата:
Верните количество не посещенных сухопутных ячеек.

😎 Решение:

public class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) dfs(grid, i, 0);
            if (grid[i][n - 1] == 1) dfs(grid, i, n - 1);
        }
        
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) dfs(grid, 0, j);
            if (grid[m - 1][j] == 1) dfs(grid, m - 1, j);
        }
        
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private void dfs(int[][] grid, int x, int y) {
        int m = grid.length, n = grid[0].length;
        if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1) {
            return;
        }
        grid[x][y] = 0;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}

Ставь 👍 и забирай 📚 Базу знаний