题目描述

在峰会期间，武装部队将高度戒备。警察将监控布拉格街道，军队将守卫建筑物，捷克领空将布满美国F-16战机。此外，军舰和战列巡洋舰将被派往伏尔塔瓦河沿岸巡逻。然而，一旦发生任何事件，捷克海军仅有少数几位舰长能够指挥大规模海战。因此，军方决定培养新一批海军将领。作为训练的一部分，他们选择了经典游戏“海战”来辅助训练。

在这个游戏中，玩家需在方形棋盘上放置若干艘矩形船只，且船只之间不能有任何接触（包括边和角）。本题中，我们仅考虑由 # 字符组成的矩形船只。给定一个矩形海域（用 $.$ 表示水，# 表示船体），请编写程序计算其中正确放置的船只数量。

输入格式

$-$输入包含多个测试场景，每个场景以两个整数 $R$ 和 $C$（$1 \leq R, C \leq 1000$）开头，分别表示海域的行数和列数。
$-$接下来的 $R$ 行，每行包含 $C$ 个字符（# 或 .），描述海域布局。
$-$输入以 $0$ $0$ 结束。

输出格式

对每个场景输出一行：
$1$. 若所有船只均为矩形且互不接触（包括对角），则输出 $"There are S ships."$（$S$ 为船只数量）。
$2$. 否则输出 $"Bad placement."$。

样例输入 1

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

样例输出 1

Bad placement.
There are 5 ships.

来源

CTU Open $2002$