P1331 Naval Battle

During the summit, the armed forces are on high alert. Police will monitor every street, the army will guard buildings, and the airspace will be filled with F-2003 aircraft. In addition, cruisers and fleets will be sent to protect the coastline. Unfortunately, for various reasons, only a few officers in the Navy can command large naval battles. Therefore, they have trained some new naval commanders. The officers chose the "Sea Battle" game to help them learn.

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.

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 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.`.

For $100\%$ of the testdata, $1 \le R, C \le 1000$. Translated by ChatGPT 5