1
\$\begingroup\$

Say I have an two dimensional array with values 0 or 1. How would I construct an algorithm (preferably in C#) to work out which ones are separated or islands. The algorithm would transform the left 2d array to look something more like the right array?

image showing the input and desired output

\$\endgroup\$
7
\$\begingroup\$

This is a standard computer science problem called connected component search.

You can solve it in time linear in the number of cells using iterated depth-first / breadth-first search or a flood fill algorithm.

  1. Walk over the cells of your grid systematically.

  2. If the cell is 0, skip ahead to the next cell.

  3. Otherwise, check if you've already visited this cell and assigned it to an island. If so, skip ahead to the next cell.

  4. Lastly, if it's a 1 not yet visited and assigned to an island, then it's the first cell of a new island. Start a depth-first (or breadth-first, or flood fill) search from this location, looking for adjacent 1 cells, then 1 cells adjacent to them, etc...

  5. For each cell you visit in this depth-first search, mark it visited, and add it to the island.

  6. Once the search bottoms-out, you've found & marked all cells in this island. Resume your systematic walk of the grid.

  7. Once you finish your systematic walk, all grid cells have been categorized into islands.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.