Description

On a square board, a fixed number of ships with fixed shapes are placed, and no ship may touch any other ship. In this problem, each ship is a square: every ship must be a solid square composed of connected # cells with sides parallel to the grid axes.

Compute the total number of ships placed on the board.

Input Format

The first line contains two integers $R$ and $C$, separated by a space, denoting the number of rows and columns of the game board.

Each of the next $R$ lines contains $C$ characters, each being # or .. # denotes a part of a ship, and . denotes water.

Output Format

Output one line. If the placement is correct (that is, the board consists only of pairwise non-touching square ships; if two # cells are vertically or horizontally adjacent but belong to two different ships, then those two ships are considered touching), output There are S ships., where $S$ is the number of ships. Otherwise, output Bad placement..

6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#

There are 5 ships.

Hint

For $100\%$ of the testdata, $1 \le R, C \le 1000$.

Translated by ChatGPT 5