# Lost at Sea

Time limit: 0.4s Memory limit: 256MB Input: Output:

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.

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

4 5
11110
11010
11000
00000


stdout

1


## Example 2

stdin

5 5
11000
11000
00000
00100
00011


stdout

2