#175MediumGraphs· Connected Components on a Grid
Count the Oil Fields
Input format
`scan`: an array of strings of equal length, each character `"0"` or `"1"`.
Output format
An integer: the number of groups of edge-connected `"1"` cells.
Examples
Input: scan = ["11000", "11000", "00100", "00011"]
Output: 3
There is a 2x2 field at the top left, a single cell in the middle, and a pair at the bottom right: 3 fields.
Input: scan = ["101", "010", "101"]
Output: 5
Cells touch only diagonally, which does not connect them, so each of the five 1s is its own field.
Input: scan = ["000", "000"]
Output: 0
No oil was detected anywhere.
Constraints
- 1 <= scan.length <= 200
- 1 <= scan[i].length <= 200
- Every row has the same length and contains only the characters 0 and 1.
Study first
- #graph
- #depth-first-search
- #matrix
- #connected-components