建议将此题做为广搜题
#include<bits/stdc++.h>
using namespace std;
bool nex[1001][1001];
int res=0;
bool b[1001][1001];
int pd(int i,int j) //如思路所述的判断两个矩阵的
{
if (nex[i][j]==1)
{
if (nex[i+1][j-1]==1)
{
if (nex[i+1][j]==0 || nex[i][j-1]==0)
{
return 1;
}
}
if (nex[i+1][j+1]==1)
{
if (nex[i+1][j]==0 || nex[i][j+1]==0)
{
return 1;
}
}
if (nex[i-1][j-1]==1)
{
if (nex[i][j-1]==0 || nex[i-1][j]==0)
{
return 1;
}
}
if (nex[i-1][j+1]==1)
{
if (nex[i-1][j]==0 || nex[i][j+1]==0)
{
return 1;
}
}
}
return 0;
}
int nexxt[4][2]={{0,1},{1,0}};
//int ue[100001];
int hx[1000001];
int hy[1000001];
int n,k;
//bool b[7777][7777];
void bfs(int x,int y)
{
int head=0,tail=1;
//nex[x][y]=0;
b[x][y]=1;
hx[tail]=x;
hy[tail]=y;
while(head<tail)
{
head++;
for(int i=0;i<2;i++)
{
int tx=hx[head]+nexxt[i][0];
int ty=hy[head]+nexxt[i][1];
if(pd(tx,ty)){
cout<<"Bad placement.";
exit(0);
}
if(tx<0||tx>=n||ty<0||ty>=k)continue;

if(nex[tx][ty]==1&&b[tx][ty]==0)
{

tail++;
hx[tail]=tx;
hy[tail]=ty;
//ue[tail]=ue[head]+1;
nex[tx][ty]=1;
b[tx][ty]=1;
}
}
}
}
int main()
{

cin>>n>>k;
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
{
char s;
s=getchar();
while(s=='\n')s=getchar();
//s=getchar();
if(s=='#')
nex[i][j]=1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<k;j++)
{
if(nex[i][j]==1&&b[i][j]==0)
{
res++;
// cout<<i<<j<<endl;
bfs(i,j);
}
}
}
cout<<"There are "<<res<<" ships.";
//getchar();
// getchar();
}