Count Islands with Diagonal Connectivity

Given a binary grid, count the connected components of cells containing 1. Two land cells are connected when their rows differ by at most one and their columns differ by at most one, so horizontal, vertical, and diagonal neighbors all connect.

Function Signature

count_islands_8(grid: list[list[int]]) -> int

Valid Input Domain

The grid is rectangular, may be empty, and contains only zero and one.

Exact Output Semantics

Return the number of eight-directionally connected land components. Empty grids and grids with no land return 0. Only the count is returned, so component order is irrelevant.

Constraints

• 0 <= rows, columns <= 1,000.
• rows * columns <= 1,000,000.

Public Examples

Example 1

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

Output: 1

The two land cells touch diagonally and therefore form one island.

Example 2

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

Output: 3

None of the three land cells is within one row and one column of another.

Hints

• A land cell has up to eight neighbors rather than four.
• Mark a cell when it enters the traversal frontier so it cannot be counted twice.