Problem 2781: Lost at Sea

Congrats! You’ve reached the point in your career when you’re the one conducting the interviews and deciding who to hire to work on your one in a million idea!

Obviously, the first thing you need are some software engineers to actually implement those insane ideas. In order to hire some, you decide to use a classic coding interview problem: figuring out the number of islands from a 2D matrix of 0s (sea) and 1s (land). The problem statement you give to your first candidate is as follows:

Given a 2D grid map of 1s (land) and 0s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally, vertically or diagonally. You may assume all four edges of the grid are all surrounded by water.

So far so good, the candidate has the perfect idea to solve this: iterating over the 2D matrix and each time it hits land, a "flooding" algorithm is used to traverse the 1s and change them 0 (thus "flooding" the land) and incrementing the island counter by $1$ . After this the matrix iteration is resumed until the end is reached.

Task

However, they have a bug in their code and the correct answer is not always returned. Given that you’re a good interviewer, you decide to correct the code and explain to them what they did wrong. Good luck!

Download the source file here or from the section "Attachments" from the sidebar.

Constraints and clarifications

You may only add/modify at most 5 lines!
Let $r$ be the number of lines and $c$ the number of columns of this matrix. $r \times c \le 1\ 000\ 000$ .

Example 1

stdin

stdout

Example 2