Number of Islands

Problem

You are given a rectangular grid where each cell is either land ('1') or water ('0'). Two land cells belong to the same island if one can be reached from the other by stepping up, down, left, or right through land cells only (diagonal steps do not connect). Everything outside the grid is water. Count how many islands the grid contains.

• The grid has at least one cell and at most 400 rows and 400 columns.
• Every cell holds exactly one of the two characters '0' and '1'.

Examples

• grid = [["1","0","0","1"],["1","0","1","1"],["0","0","0","0"],["1","1","0","1"]] → 4. The two cells in the left column form one island, the three cells in the top-right corner form another, and the bottom row holds two separate islands split by a water cell.
• grid = [["1","1","1"],["1","0","1"],["1","1","1"]] → 1. A ring of land around a single water cell is still one connected piece.
• grid = [["1","0","1","0","1","0"],["0","1","0","1","0","1"]] → 6. A checkerboard: every land cell touches the others only at corners, so each one is its own island.

Hints

1. Think of each land cell as a node and each pair of orthogonally adjacent land cells as an edge. What graph question is being asked?
2. Once you touch one cell of an island, how do you make sure you never count any of its other cells again?
3. Count connected components: scan the grid, and every time you find unvisited land, flood-fill (DFS or BFS) the whole island and mark it visited.