Loading
Loading
A marine survey divides a stretch of sea into square cells and marks each one as coral (1) or open water (0). Coral cells that touch along a side belong to the same reef; cells that only touch at a corner do not.
Return the number of separate reefs in chart.
chart = [[1,1,0,0,1],[1,0,0,1,1],[0,0,1,0,0],[1,0,1,1,0]]reef 1(0,0) (0,1) (1,0) — top-leftreef 2(0,4) (1,3) (1,4) — top-rightreef 3(2,2) (3,2) (3,3) — centrereef 4(3,0) — a single cell4Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 1 | 0 | 0 | 1 |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 |
| 3 | 1 | 0 |
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(rows × cols) time · O(rows × cols) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 1 | 0 | 0 | 1 |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 |
| 3 | 1 | 0 | 1 | 1 | 0 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
| 1 |
| 1 |
| 0 |
Example 2
| 0 | 1 | 0 | 1 |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 1 |
Diagonal neighbours do not join, so every reef cell stands alone.
Example 3
| 0 | 0 | 0 |
|---|---|---|
| 1 | 0 | 0 |
Open water everywhere.