#6MLE,#11WA,求调
#pragma GCC optimize(3)
#include<iostream>
#include<queue>
using namespace std;
typedef unsigned long long int UL;
typedef long long int LL;
typedef unsigned short US;
typedef double DB;
struct Node
{
LL x;
LL y;
};
char sea[1002][1002]={0};
bool visited[1002][1002]={false};
LL BFS(LL y,LL x)
{
queue<Node> q;
LL minx=999999999,maxx=0,miny=999999999,maxy=0;
Node node;
node.x=x;
node.y=y;
q.push(node);
while (q.empty()!=true)
{
node=q.front();
q.pop();
visited[node.y][node.x]=true;
if (sea[node.y-1][node.x]=='#'&&visited[node.y-1][node.x]!=true)
{
node.y=node.y-1;
node.x=node.x;
if (node.x<minx)
minx=node.x;
if (node.y>maxy)
maxy=node.y;
if (node.x>maxx)
maxx=node.x;
if (node.y<miny)
miny=node.y;
q.push(node);
}
if (sea[node.y+1][node.x]=='#'&&visited[node.y+1][node.x]!=true)
{
node.y=node.y+1;
node.x=node.x;
if (node.x<minx)
minx=node.x;
if (node.y>maxy)
maxy=node.y;
if (node.x>maxx)
maxx=node.x;
if (node.y<miny)
miny=node.y;
q.push(node);
}
if (sea[node.y][node.x-1]=='#'&&visited[node.y][node.x-1]!=true)
{
node.y=node.y;
node.x=node.x-1;
if (node.x<minx)
minx=node.x;
if (node.y>maxy)
maxy=node.y;
if (node.x>maxx)
maxx=node.x;
if (node.y<miny)
miny=node.y;
q.push(node);
}
if (sea[node.y][node.x+1]=='#'&&visited[node.y][node.x+1]!=true)
{
node.y=node.y;
node.x=node.x+1;
if (node.x<minx)
minx=node.x;
if (node.y>maxy)
maxy=node.y;
if (node.x>maxx)
maxx=node.x;
if (node.y<miny)
miny=node.y;
q.push(node);
}
}
for (LL x1=minx;x1<=maxx;x1++)
{
for (LL y1=miny;y1<=maxy;y1++)
{
if (sea[y1][x1]!='#')
return -1;
}
}
return 1;
}
int main()
{
ios::sync_with_stdio(false);
LL n,m,flag,sum=0;
cin>>n>>m;
for (LL n1=1;n1<=n;n1++)
{
for (LL m1=1;m1<=m;m1++)
{
cin>>sea[n1][m1];
}
}
for (LL n1=1;n1<=n;n1++)
{
for (LL m1=1;m1<=m;m1++)
{
if (sea[n1][m1]=='#'&&visited[n1][m1]==false)
{
flag=BFS(n1,m1);
if (flag==-1)
{
cout<<"Bad placement."<<endl;
return 0;
}
else
sum++;
}
}
}
cout<<"There are "<<sum<<" ships."<<endl;
return 0;
}