可以把图的周围全包上一圈'.' 遍历图中每个点 可知当图中存在一下四种结构中的一个时 必有船相撞 输出并退出循环 否则则dfs这个点 若图中不存在这些结构 就可以输出连通块数量即轮船数了

#include<cstdio>
#include<cstring>
using namespace std;
 
const int N=1005;
char mat[N][N];bool vis[N][N];
int x[4]= {-1,1,0,0},y[4]= {0,0,-1,1};
 
bool isBad(int i,int j)
{
    if(mat[i][j]=='.'&&mat[i-1][j]=='#'&&mat[i][j-1]=='#') return 1;
    if(mat[i][j]=='.'&&mat[i-1][j]=='#'&&mat[i][j+1]=='#') return 1;
    if(mat[i][j]=='.'&&mat[i+1][j]=='#'&&mat[i][j-1]=='#') return 1;
    if(mat[i][j]=='.'&&mat[i+1][j]=='#'&&mat[i][j+1]=='#') return 1;
    return 0;
}
 
int dfs(int i,int j)
{
    if (vis[i][j]||mat[i][j]=='.') return 0;
    vis[i][j]=true;
    for(int k=0; k<4; ++k)
        if(mat[i+x[k]][j+y[k]]=='#') dfs(i+x[k],j+y[k]);
    return 1;
}
 
int main()
{
    int i,j,n,m;
    while(scanf("%d%d",&n,&m),n)
    {
        for(i=1; i<=n; ++i)
            scanf("%s",mat[i]+1);
        for(i=0; i<=n+1; ++i)  mat[i][0]=mat[i][m+1]='.';
        for(j=0; j<=m+1; ++j)  mat[0][j]=mat[n+1][j]='.';
        int ans=0;
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; ++i)
        {
            for(j=1; j<=m; ++j)
                if(isBad(i,j)) break;
                else ans+=dfs(i,j);
            if (j<=m) break;
        }
 
        if(i<=n)
        {
            printf("Bad placement.\n");
            continue;
        }
 
        printf("There are %d ships.\n",ans);
    }
    return 0;
}