180. Number of Islands
You receive a rectangular character grid grid in which '1' marks land and '0' marks water. Two land cells belong to the same island when they share an edge — up, down, left, or right. Touching only at a corner does not connect them, and everything beyond the grid border counts as water.
Return the number of distinct islands in the grid.
The grid is really a graph in disguise: each land cell is a vertex, each shared edge between land cells is an edge, and the answer is the number of connected components.
Example 1:
Input: grid = ["11110", "11010", "11000", "00000"]
Output: 1
Explanation: All the 1s connect through shared edges into a single land mass.
Example 2:
Input: grid = ["11000", "11000", "00100", "00011"]
Output: 3
Explanation: The 2×2 block, the lone middle cell, and the pair in the bottom-right are separated by water — the middle cell touches the others only diagonally, which doesn't count.
Constraints:
- 1 ≤ m, n ≤ 300
- grid[i][j] is '0' or '1'
Hints:
When you find an unvisited land cell, you have discovered a new island — but you must then mark ALL of its cells as visited so you never count that island again.
Flood fill does exactly that: from the discovered cell, repeatedly spread to edge-adjacent land (a stack or queue works) and sink every reached cell by flipping it to '0' or marking it visited.
Alternatively, start with count = number of land cells and union every pair of edge-adjacent land cells in a disjoint-set structure; each union that merges two different sets reduces the count by one.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = ["11110", "11010", "11000", "00000"]
Expected output: 1