Number of Islands
Module 15 · Matrix / 2D Traversal
Problem
Given an m × n binary grid where '1' is land and '0' is water,
return the number of islands — a group of '1's connected
4-directionally (horizontally or vertically, not diagonally). All
four edges of the grid are assumed to be surrounded by water.
(LeetCode 200.)
Examples
Example 1
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]Output1Example 2
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]Output3Constraints
1 ≤ m, n ≤ 300, each cell is'0'or'1'.
Attempt it first
This is the direction-vector technique from the Grid Representation
concept lesson, applied to a new question: not "visit every neighbor"
but "visit every cell reachable from a starting cell." Before opening
anything, try to answer: if you land on an unvisited '1', how do you
mark an entire connected blob of land as counted, without re-counting
it, and without walking off the grid?