Problem Statement

Given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell, return the number of land cells in grid from which you can't reach to the boundary in any number of moves.

In a single move, you can walk from one cell to any cell, which is 4-directionally adjacent to the current cell.

Examples

Example 1:

• Input: grid =

[[0, 0, 0, 1],
 [1, 0, 1, 0],
 [0, 1, 1, 0],
 [0, 0, 0, 0]]

• Output: 3
• Justification: The three land cells in the center, which are at (1, 2), (2, 1), and (2, 2) positions, are surrounded by sea cells and cannot reach the boundary.

Example 2:

• Input: grid =

[[0, 1, 0],
 [1, 1, 1],
 [0, 1, 0]]

• Output: 0
• Justification: All land cells can connect to the edge either directly or through other land cells.

Example 3:

• Input: grid =

[[0, 0, 0, 0, 0],
 [0, 1, 1, 1, 0],
 [0, 1, 0, 1, 0],
 [0, 1, 1, 1, 0],
 [0, 0, 0, 0, 0]]

• Output: 8
• Justification: The eight land cells in the middle are surrounded by sea cells and cannot reach the boundary.

Constraints:

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

Solution

To solve this problem, we need to find land cells that are completely enclosed by sea cells. Our approach starts by identifying and marking all land cells connected to the boundary. These boundary-connected cells can potentially reach the sea, so we eliminate them from consideration. Next, we count the remaining land cells that are not connected to the boundary. This ensures that we only count land cells that are truly surrounded.

Using Depth-First Search (DFS) for this problem is effective because it allows us to explore and mark all connected land cells starting from any boundary cell. By systematically marking these cells, we can then simply count the unmarked land cells to get our answer. This method ensures we efficiently traverse the grid while accurately identifying and excluding boundary-connected cells.

Step-by-Step Algorithm

To solve the problem of counting land cells that cannot reach the boundary, we can follow these steps:

1. Initialize Variables:

   • Get the number of rows (rows) and columns (cols) in the grid.
   • Define a helper function dfs for performing depth-first search.

2. Mark Boundary-Connected Land Cells:

   • Iterate through the first and last columns of each row. If a cell contains land (1), call the dfs function to mark all connected land cells as sea (0).
   • Iterate through the first and last rows of each column. If a cell contains land (1), call the dfs function to mark all connected land cells as sea (0).

3. Depth-First Search (DFS) Function:

   • The dfs function should take the grid and the current cell's coordinates (i, j) as arguments.
   • If the cell is out of bounds or is sea (0), return.
   • Mark the current cell as sea (0).
   • Recursively call dfs for the cells to the right, left, down, and up of the current cell.

4. Count Enclaved Land Cells:

   • Initialize a variable count to 0.
   • Iterate through each cell in the grid. If a cell contains land (1), increment the count.

5. Return the Count:

   • Return the final count of land cells that cannot reach the boundary.

Algorithm Walkthrough

Let's walk through the example grid:

[[0, 0, 0, 1], 
 [1, 0, 1, 0], 
 [0, 1, 1, 0], 
 [0, 0, 0, 0]]

1. Initialize Variables:

   • rows = 4
   • cols = 4

2. Mark Boundary-Connected Land Cells:

   • First column:
     • grid[0][0] is sea (0).
     • grid[1][0] is land (1). Call dfs(1, 0).
       • Inside dfs(1, 0): Mark grid[1][0] as sea (0).
       • Check down: dfs(2, 0) → grid[2][0] is sea (0).
       • Check up: dfs(0, 0) → grid[0][0] is sea (0).
       • Check right: dfs(1, 1) → grid[1][1] is sea (0).
       • Check left: dfs(1, -1) → Out of bounds.
     • grid[2][0] is sea (0).
     • grid[3][0] is sea (0).
   • Last column:
     • grid[0][3] is land (1). Call dfs(0, 3).
       • Inside dfs(0, 3): Mark grid[0][3] as sea (0).
       • Check down: dfs(1, 3) → grid[1][3] is sea (0).
       • Check up: dfs(-1, 3) → Out of bounds.
       • Check right: dfs(0, 4) → Out of bounds.
       • Check left: dfs(0, 2) → grid[0][2] is sea (0).
     • grid[1][3] is sea (0).
     • grid[2][3] is sea (0).
     • grid[3][3] is sea (0).
   • First row:
     • grid[0][0] is sea (0).
     • grid[0][1] is sea (0).
     • grid[0][2] is sea (0).
     • grid[0][3] is sea (0).
   • Last row:
     • grid[3][0] is sea (0).
     • grid[3][1] is sea (0).
     • grid[3][2] is sea (0).
     • grid[3][3] is sea (0).

3. Count Enclaved Land Cells:

   • Initialize count = 0.
   • Iterate through the grid:
     • grid[0][0] is sea (0).
     • grid[0][1] is sea (0).
     • grid[0][2] is sea (0).
     • grid[0][3] is sea (0).
     • grid[1][0] is sea (0).
     • grid[1][1] is sea (0).
     • grid[1][2] is land (1). Increment count to 1.
     • grid[1][3] is sea (0).
     • grid[2][0] is sea (0).
     • grid[2][1] is land (1). Increment count to 2.
     • grid[2][2] is land (1). Increment count to 3.
     • grid[2][3] is sea (0).
     • grid[3][0] is sea (0).
     • grid[3][1] is sea (0).
     • grid[3][2] is sea (0).
     • grid[3][3] is sea (0).

4. Return the Count:

   • The final count of land cells that cannot reach the boundary is 3.

Therefore, the output for the grid [[0, 0, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]] is 3.

Code