Number of Enclaves

Problem Statement

In this task, you are provided with a matrix of dimensions m x n, comprised exclusively of binary elements where 0 symbolizes a sea cell and 1 symbolizes a land cell. The challenge involves navigating this grid with a movement mechanism that allows transition from one land cell to another land cell which is directly adjacent in any of the four cardinal directions (north, south, east, or west). Additionally, a move can also involve stepping out of the grid's boundaries if on a boundary land cell.

Your objective is to determine the total number of land cells in the provided grid from which it is impossible to step out of the grid's boundary, even after potentially multiple moves.

Examples

Example 1

Input:

grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output:

3

Explanation:

There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Example 2

Input:

grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

Output:

0

Explanation:

All 1s are either on the boundary or can reach the boundary.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] is either 0 or 1.

Approach and Intuition

Given the nature of the problem, the solution fundamentally revolves around identifying land cells that are completely enclosed by sea cells, preventing any potential escape from the grid's confines. The task then is to correctly identify and count these "trapped" land cells where no path to the boundary exists. To systematically approach this:

1. Begin by traversing each boundary row and column of the grid to identify land cells on the edges. These cells inherently have the potential to escape, and by initiating a Depth-First Search (DFS) or Breadth-First Search (BFS) from them, we can mark all directly or indirectly connected land cells as escapable.

2. Remember that during this boundary exploration, whenever a land cell is encountered:

   • Initiate a DFS/BFS from this cell to explore all connected land cells.
   • Mark all these cells during the traversal process as escapable.

3. Post traversal, any land cell that remains unmarked is identified as a trapped land cell, i.e., a cell from which an agent cannot escape to the grid's boundary.

4. Count all such unmarked land cells to determine the solution to the problem.

From the given examples, one should note:

• Any land cell touching the boundary directly or having a path to the boundary (through other land cells) can potentially move out of the grid. Hence, such cells should not be counted in the final result.
• Entirely surrounded land cells, with no access to the grid's boundary, satisfy the conditions of the problem and should be counted.

Given the problem constraints, ensuring that the solution operates efficiently within the upper bounds, even though the input size can grow quite significant, is important because multiple full-grid traversals may be necessary. An efficient graph traversal algorithm proves essential in achieving this.

Solutions

class Solver {
public:
    void breadthFirstSearch(int row, int col, int row_count, int col_count, vector<vector<int>>& area, vector<vector<bool>>& checked) {
        queue<pair<int, int>> queue;
        queue.push({row, col});
        checked[row][col] = true;
    
        vector<int> delta_x{0, 1, 0, -1};
        vector<int> delta_y{-1, 0, 1, 0};
    
        while (!queue.empty()) {
            int curr_row = queue.front().first;
            int curr_col = queue.front().second;
            queue.pop();
    
            for (int i = 0; i < 4; i++) {
                int new_row = curr_row + delta_x[i];
                int new_col = curr_col + delta_y[i];
                if (new_row < 0 || new_row >= row_count || new_col < 0 || new_col >= col_count) {
                    continue;
                } else if (area[new_row][new_col] == 1 && !checked[new_row][new_col]) {
                    queue.push({new_row, new_col});
                    checked[new_row][new_col] = true;
                }
            }
        }
    }
    
    int countEnclaves(vector<vector<int>>& area) {
        int row_count = area.size();
        int col_count = area[0].size();
        vector<vector<bool>> checked(row_count, vector<bool>(col_count));
    
        for (int row = 0; row < row_count; ++row) {
            if (area[row][0] == 1 && !checked[row][0]) {
                breadthFirstSearch(row, 0, row_count, col_count, area, checked);
            }
            if (area[row][col_count - 1] == 1 && !checked[row][col_count - 1]) {
                breadthFirstSearch(row, col_count - 1, row_count, col_count, area, checked);
            }
        }
    
        for (int col = 0; col < col_count; ++col) {
            if (area[0][col] == 1 && !checked[0][col]) {
                breadthFirstSearch(0, col, row_count, col_count, area, checked);
            }
            if (area[row_count - 1][col] == 1 && !checked[row_count - 1][col]) {
                breadthFirstSearch(row_count - 1, col, row_count, col_count, area, checked);
            }
        }
    
        int enclave_count = 0;
        for (int row = 0; row < row_count; row++) {
            for (int col = 0; col < col_count; col++) {
                if (area[row][col] == 1 && !checked[row][col]) {
                    enclave_count++;
                }
            }
        }
        return enclave_count;
    }
};