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 ```python 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** ```text 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** ```text 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** ```text 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.