Daily bit(e) of C++ | Counting islands
Daily bit(e) of C++ #170, Common interview problem: Counting islands.
Today we will look at a common C++ interview problem: Counting islands.
Given a map as a std::vector<std::vector<char>> where 'L' represents land and 'W' represents water, return the number of islands on the map.
An island is an orthogonally (four directions) connected area of land spaces that is fully (orthogonally) surrounded by water.
For example, in the above map, we only have one island since no other land masses are fully surrounded by water.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/Y8o6ahK41.
Solution
We will need two distinct pieces of functionality.
We need to scan the map to discover land spaces.
Once we have a land space, we need to determine the full extent of this land mass and determine whether this is an island.
A land mass is an island if we don’t reach the border of our map during our exploration. Importantly, as we scan for land spaces, we must avoid spaces we have already visited during our exploration (to avoid double-counting islands).
To explore islands, we can use a depth-first or breadth-first search; this solution relies on a depth-first search. As long as we explore each island fully and keep track of visited spaces, we do not have to worry about double-counting.
