Understanding the Problem
We are given a 2D grid where 1
represents land and 0
represents water. Our task is to count the number of land cells that are completely enclosed — meaning they cannot reach the boundary of the grid by moving up, down, left, or right. These enclosed land cells are called enclaves.
To solve this, we need to eliminate all land cells that can possibly escape to the boundary. The remaining land cells are the enclaves.
Step-by-Step Solution with Example
Step 1: Identify the Boundaries
We start by identifying all the cells on the outer border of the grid — i.e., the first and last rows, and the first and last columns. Any land cell (1
) that is on the boundary or connected to the boundary is not an enclave.
Step 2: Traverse from Boundary Land
We perform a DFS (or BFS) starting from each boundary land cell to mark all reachable land cells. These cells will be marked as visited. This step helps us eliminate all land that can reach the boundary directly or indirectly.
Step 3: Count Unvisited Land Cells
After marking all boundary-connected land, we loop through the grid. Any land cell that is still unvisited is an enclave. We count these and return the total.
Step 4: Example Walkthrough
Consider the grid:
[
[0, 0, 0, 0],
[1, 0, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]
]
Let's analyze this:
- None of the boundary cells are land (except corners but they are water).
- Start DFS from any boundary land — in this case, there is none, so we skip DFS.
- Check internal cells: (1,0) is land but on edge — count it out; (1,2), (2,1), and (2,2) are land and cannot reach boundary. They are enclaves.
Final Count = 3 enclaves.
Edge Cases
- Empty Grid: If the grid has no rows or columns, return 0 — no land exists.
- All Zeros: A grid filled with water returns 0 — no land to begin with.
- All Boundary Land: If all land is on the edge or connected to it, return 0 — no enclaves possible.
- All Land Surrounded by Water: Internal land cells completely boxed in by water are counted — this is a valid enclave case.
Finally
This problem teaches us how to separate the problem space based on what we can eliminate (boundary-connected land) rather than directly searching for enclaves. Using DFS or BFS to eliminate reachable land from the edge is an efficient and intuitive approach. Beginners should understand the importance of boundary analysis and traversal techniques in grid problems.
Comments
Loading comments...