Medium graphs · flood fill · grids

Count the islands

A satellite map of an archipelago. Count the islands without counting any of them twice.

Write countIslands(grid): grid is rows of 0 (water) and 1 (land). An island is land connected up, down, left or right. Return how many islands there are.

As you find each island, mark its cells as 2 in a copy of the grid and call show(copy). The stage draws water, land and counted land in three colours.

Example: countIslands([[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1]]) returns 3.

Tests you can see

countIslands([[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]])1
countIslands([[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]])3

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptcountIslands()

function countIslands(grid) {
  const g = grid.map((r) => [...r]);
  let count = 0;
  // find a 1, count it, sink the whole island to 2, show(g)
  return count;
}

function countIslands(grid) {
  const g = grid.map((r) => [...r]);
  let count = 0;
  // find a 1, count it, sink the whole island to 2, show(g)
  return count;
}

Tab indents · Cmd/Ctrl+Enter runs