Space Mission
Limits: 2 sec., 256 MiB
Space telescope Hubble just sent back some photos of the planet where aliens reside. To have an idea about their population, you want to count the number of houses in the photos. But aliens have strange land architecture. They like to build a lot of walls of strange form.
The blocks are connected only if they share an edge. Connected blocks represent either the wall or the house. Unfortunately, you can’t differentiate the wall and house in the picture. The only thing you know is that the walls must surround some free space inside; otherwise, it is a house.
Count the number of houses in the photo.
Input
The first line of the input contains two integers \(n\) and \(m\) – height and width of the photo.
The next \(n\) lines contains \(m\) characters each, each character is
either .
(free cell) or #
(block). The
perimeter of the photo contains only free cells.
Output
One integer – the number of houses on the photo.
Constraints
\(3 \le n, m \le 10^{3}\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 7 ....... .###.#. ..##.#. ....... | 2 |
Input (stdin) | Output (stdout) |
---|---|
5 9 ......... ..#..###. .#.###.#. ..#..###. ......... | 3 |
Input (stdin) | Output (stdout) |
---|---|
9 8 ........ .######. .##.#.#. .#.#.##. .##.#.#. .#.#.##. .##.#.#. .######. ........ | 3 |
Input (stdin) | Output (stdout) |
---|---|
5 5 ..... .###. .#.#. .##.. ..... | 1 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|