Vultr DocsLatest Content

Number of Enclaves

Updated on 26 June, 2025
Number of Enclaves header image

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

  • C++
  • Java
cpp 
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;
    }
};

This C++ solution tackles the problem of counting enclaves in a 2D grid. An enclave is defined as a group of connected 1s that are completely surrounded by water (0s) and not accessible from the grid's edges.

  • The code structure involves two main public functions in the Solver class:

    • breadthFirstSearch: This method helps in exploring the grid from a specific cell using a queue data structure to achieve the breadth-first search (BFS) approach. It uses two arrays, delta_x and delta_y, to navigate through the grid's four possible directions (up, down, left, and right).
    • countEnclaves: This function initializes a boolean grid checked to track visited cells and iterates over the grid's borders (both rows and columns). It employs the breadthFirstSearch function on the unvisited 1s to mark reachable cells from edges. Subsequently, it counts and returns the number of unvisited 1s inside the grid, which represents the enclaves.

  • The steps for the algorithm are:

    1. Initialize tracking for visited/unvisited nodes.
    2. Use a BFS starting from boundary nodes that are 1s to mark reachable nodes.
    3. After identifying the reachable nodes from boundaries, traverse the entire grid. Count the nodes that are 1s and also unvisited, which will give the enclaves' count.

  • The main() method in the typical usage of this class would create an instance of Solver, initialize a grid with the 2D area, and then call countEnclaves to get the number of isolated regions completely surrounded by water.

This approach ensures efficient inspection of grid boundaries and internal areas, effectively counting enclaves using grid traversal techniques while leveraging BFS for exploring connected components.

java 
class Solution {
    public void explore(int row, int col, int rows, int cols, int[][] matrix, boolean[][] visited) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{row, col});
        visited[row][col] = true;

        int[] dx = {0, 1, 0, -1};
        int[] dy = {-1, 0, 1, 0};

        while (!queue.isEmpty()) {
            int[] currentPosition = queue.poll();
            row = currentPosition[0];
            col = currentPosition[1];

            for (int k = 0; k < 4; k++) {
                int newRow = row + dx[k];
                int newCol = col + dy[k];
                if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) {
                    continue;
                } else if (matrix[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                    queue.add(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
    }

    public int countEnclaves(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int i = 0; i < rows; ++i) {
            if (matrix[i][0] == 1 && !visited[i][0]) {
                explore(i, 0, rows, cols, matrix, visited);
            }
            if (matrix[i][cols - 1] == 1 && !visited[i][cols - 1]) {
                explore(i, cols - 1, rows, cols, matrix, visited);
            }
        }

        for (int j = 0; j < cols; ++j) {
            if (matrix[0][j] == 1 && !visited[0][j]) {
                explore(0, j, rows, cols, matrix, visited);
            }
            if (matrix[rows - 1][j] == 1 && !visited[rows - 1][j]) {
                explore(rows - 1, j, rows, cols, matrix, visited);
            }
        }

        int enclaveCount = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 1 && !visited[r][c]) {
                    enclaveCount++;
                }
            }
        }
        return enclaveCount;
    }
}

This Java solution addresses the problem of counting the number of enclaves in a 2D grid. Enclaves are groups of neighboring ones (1s) that are completely surrounded by water (0s) except at the grid's border. The code implements a flood fill algorithm using a breadth-first search (BFS) approach to identify areas that are not enclaves by marking the connected regions of 1s starting from the grid's border. The primary steps involved are as follows:

  1. Define a nested explore method to perform BFS starting from a given cell that contains a 1. This method places its start position into a queue and processes each position, exploring its neighboring cells in four directions (left, up, right, down). Cells are marked as visited once they are processed, ensuring no cell is revisited.

  2. The main method, countEnclaves, initializes a visited matrix to keep track of processed cells and iterates over the entire grid. It particularly focuses on cells at the borders (first and last rows, first and last columns) and calls the explore method for every unvisited 1 found.

  3. After all possible non-enclave regions have been marked via the first pass using the explore function, the code proceeds to count the remaining unvisited 1s within the grid. These account for the enclaves, as they are surrounded by zeros or the outer boundaries.

  4. The output, enclaveCount, is the total number of 1s that have not been visited after the first exploration pass, thus counting the number of enclaves in the grid.

Comments

No comments yet.