此题源于洛谷P1331
链接奉上qwq：P1331
题目描述
在峰会期间，武装部队得处于高度戒备。警察将监视每一条大街，军队将保卫建筑物，领空将布满了F-2003飞机。此外，巡洋船只和舰队将被派去保护海岸线。不幸的是因为种种原因，国防海军部仅有很少的几位军官能指挥大型海战。因此，他们考虑培养一些新的海军指挥官，他们选择了“海战”游戏来帮助学习。
在这个著名的游戏中，在一个方形的盘上放置了固定数量和形状的船只，每只船却不能碰到其它的船。在这个题中，我们仅考虑船是方形的，所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。
输入输出格式
输入格式：
输入文件头一行由用空格隔开的两个整数R和C组成，1<=R,C<=1000，这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符，每个字符可以为“#”，也可为“.”，“#”表示船只的一部分，“.”表示水。
输出格式：
为每一个段落输出一行解。如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。
输入输出样例
输入样例#1：
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#输出样例#1：
There are 5 ships.这题是在模拟测试的时候做到的，因为我们班级的人很蒟蒻而且主要是普及的题目，所以这道题目是压轴题qwq
啊哈哈哈哈哈万分没想到的是我过了！我过了！
【思路】
主要也要看自己的阅读能力吧......
注意这句话“我们仅考虑船是方形的，所有的船只都是由图形组成的方形”，说明一条船是由最大的#所组成的方形矩阵！
这道题我的想法也就是按照BFS入门题目的填涂颜色还有那个什么细胞分裂的想法一样的，算出连在一起的‘#‘的个数，而这个连在一起的个数就是最后船的个数。
但是这里要判断如果两艘船相邻，这个就比较恶心了，这个相邻的意思就是有两个方形矩阵相邻，且这两个方形无法组成新的方形。
比如下图就是一种例子：
虽然这两个方形有部分相连，但是他们并不是同一个方形，所以这就是两个船，即第一个红方框围成的一个船，第二个红方框围成的一个船。
这里如果两个船相邻仅需要输出Bad placement.就可以了，这时候我们便可以使用一点点贪心（不是贪心算法的那个意思）
在BFS搜索的时候判断有没有以下情况，如果有的话那么就直接跳出搜索，直接输出Bad placement.
我们可以找一找规律，便可以发现如果两个#有以下情况：
【代码】
#include <stdio.h>
#include <string.h>
int dx[2][2]={{0,1},{1,0}}; //剪枝，不一定非要判断上下左右，只用判断右和下，因为左，下是已经判断过的，在判断一次就大大多了循环时间
int que[1000001][2],b[1001][1001],a[1001][1001],n,m,l;
/* que是队列，b是存储是否走过，a是存储原本的.#,
n,m是边界，l是判断是否有两个相邻的船，方便输出*/
int pd(int i,int j) //如思路所述的判断两个矩阵的
{
if (a[i][j]==1)
{
if (a[i+1][j-1]==1)
{
if (a[i+1][j]==0 || a[i][j-1]==0)
{
return 1;
}
}
if (a[i+1][j+1]==1)
{
if (a[i+1][j]==0 || a[i][j+1]==0)
{
return 1;
}
}
if (a[i-1][j-1]==1)
{
if (a[i][j-1]==0 || a[i-1][j]==0)
{
return 1;
}
}
if (a[i-1][j+1]==1)
{
if (a[i-1][j]==0 || a[i][j+1]==0)
{
return 1;
}
}
}
return 0;
}
void BFS(int x,int y,int k) //BFS，这里的k可以省略，因为没什么用
{
int tail=1,head=0,i,x1,y1;
que[tail][0]=x;
que[tail][1]=y; //源结点入队列
b[x][y]=1; //标记判断过
do
{
head++;
for (i=0;i<2;i++)
{
x1=que[head][0]+dx[i][0];
y1=que[head][1]+dx[i][1]; //扩展的坐标
if (pd(x1,y1)==1)
{
l=1;
return ;
} //先判断旁边有没有别的船是相邻的，有的话就不用搜索了
if (x1>=1 && x1<=n && y1>=1 && y1<=m && a[x1][y1]==1 && b[x1][y1]==0) //判断边界，判断走没走过，判断是不是#
{
tail++;
que[tail][0]=x1;
que[tail][1]=y1; //拓展新的结点
b[x1][y1]=1; //标记走过
a[x1][y1]=k; //这里是为了辨别别的船，根据推敲，也不需要这一行，因为b数组的作用已经体现了，因此整个函数的int k也可以删去的
}
}
}while (head<tail);
}
int main()
{
char ch[10001];
int total=0,i,j,k=1;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%s",ch); //输入的格式没有空格，因此需要先录入一个字符串
for (j=0;j<=strlen(ch)-1;j++) //进行字符串存储到a数组里
{
if (ch[j]=='#')
a[i][j+1]=1; //如果是船体的一部分#
else //如果是海“.”
a[i][j+1]=0;
}
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++) //搜索
{
if (a[i][j]==1 && b[i][j]==0) //如果这个地方是船体，并且没有走过
{
k++; //可不要
BFS(i,j,k); //进行循环，将这里这一片所连在一起的#进行标记判断
total++; //船数量+1
}
}
}
if (l==1)
{
printf("Bad placement.\n");
} //如果有船体相邻的
else
printf("There are %d ships.\n",total); //否则就输出船只数
return 0;
}【反思及注意点】
这道题考试的时候没有花太多的时间在标记船的部分，主要在推相邻船只那里用了点时间，可能不是最优的算法，所以希望大佬不要喷！
以上就是蒟蒻题解的全部内容啦！
原文：https://www.cnblogs.com/CZPeng/p/11306040.html