Count Grid Islands That Never Touch the Border

You are given a rectangular grid in which 0 marks a land cell and 1 marks a water cell. An island is a maximal group of land cells connected horizontally or vertically. An island is enclosed when water surrounds it on every side inside the grid, that is, when none of its cells lies on the border of the grid. Return the number of enclosed islands.

Function Signature

def count_enclosed_islands(grid: list[list[int]]) -> int:

Rules

• Cells (r, c) and (r2, c2) are adjacent when they share an edge: abs(r - r2) + abs(c - c2) == 1. Diagonal cells are not adjacent, so land cells that touch only at a corner belong to different islands.
• With m rows and n columns, the border cells are those in row 0, row m - 1, column 0 or column n - 1. The area outside the grid does not count as water: an island with at least one border cell is not enclosed.
• Every enclosed island counts once, whatever its size or shape.

Constraints

• 1 <= m = len(grid) <= 100 and 1 <= n = len(grid[0]) <= 100; all rows have the same length.
• Every grid[r][c] is 0 or 1.
• The answer is an integer between 0 and m * n.

Examples

Example 1

Input: grid = [[1, 1, 1, 1, 1, 0],
 [1, 0, 0, 1, 1, 0],
 [1, 0, 1, 1, 0, 1],
 [1, 1, 1, 0, 0, 1],
 [0, 0, 1, 1, 1, 1]]
Output: 2

There are four islands. {(1, 1), (1, 2), (2, 1)} and {(2, 4), (3, 3), (3, 4)} have no border cell, so they are enclosed. {(0, 5), (1, 5)} and {(4, 0), (4, 1)} lie on the border.

Example 2

Input: grid = [[1, 1, 1, 1],
 [1, 0, 1, 1],
 [1, 1, 0, 1],
 [1, 1, 1, 0]]
Output: 2

The land cells (1, 1), (2, 2) and (3, 3) touch only diagonally, so they form three separate islands. (1, 1) and (2, 2) are enclosed; (3, 3) is a border cell.

Example 3

Input: grid = [[1, 1, 1, 1, 1],
 [1, 0, 0, 0, 1],
 [1, 0, 1, 0, 1],
 [1, 0, 0, 0, 0],
 [1, 1, 1, 1, 1]]
Output: 0

All nine land cells form one ring-shaped island. It reaches the border only through the cell (3, 4) in the last column, but that is enough: the island is not enclosed.