How Graphs work

Before you start

• BFS for levels

  Graphs reuse the two tree walks, depth-first and breadth-first, plus a way to avoid revisiting nodes.

  Open lesson

Why it matters

Satellite imagery, game maps, and segmentation tools often need to count separate regions in a grid. Repeatedly propagating region labels can rescan a long connected shape many times and turn a map-sized input into quadratic work. Every cell may be inspected only a constant number of times, and every connected land region must be counted exactly once.

grid is '1' land and '0' water. An island is 4-connected land. Return the number of islands.

Input

grid = [["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"]]

Output

3

In the 4 × 5 grid, brute relabeling revisits the four-cell island until labels stabilize. A single flood from (0, 0) marks all four cells; floods from (2, 2) and (3, 3) then produce the final count 3.

In the 4 × 5 grid, the scan first reaches land at (0, 0). Count 1, then sink (0, 0), (0, 1), (1, 0), and (1, 1) by changing each "1" to "0" before visiting its four neighbors.

The scan skips those changed cells, then finds untouched land at (2, 2) for count 2. Land at (3, 3) starts count 3 and its walk also sinks (3, 4). Marking before recursion prevents a walk from circling back and prevents the outer scan from counting a region twice.