Lean4

38. Number of islands

MediumProgramAcademy Pass20 points

grid is a rectangle of cells, given row by row: 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically; diagonal neighbours do not connect.

Write numIslands grid, the number of islands.

Examples

  1. InputnumIslands [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1]]Output3
  2. InputnumIslands [[1, 1, 1], [0, 1, 0], [1, 1, 1]]Output1
  3. InputnumIslands [[1, 0], [0, 1]]Output2

Submitting also runs 9 hidden tests.

Constraints

  • All rows have the same length. Hidden tests include grids of 200 × 200 cells.
gridsgraph searcharrays

Running and submitting solutions, the hints and the editorial come with the Academy Pass. The daily problem is open to every account.

Learn the ideas

Similar problems

Solution.lean
Loading…
Loading editor…
3#guard (numIslands [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1]]) = (3)
4#guard (numIslands [[1, 1, 1], [0, 1, 0], [1, 1, 1]]) = (1)
5#guard (numIslands [[1, 0], [0, 1]]) = (2)
examples

Run checks your code against the examples and your custom inputs and records nothing. Submit also runs the hidden tests, confirms the axioms your proof uses and records the result. Each uses one compiler check.

ReadyLn 1, Col 1Lean 4
Draft saved in this browser