🏆今日学习目标：
🍀学习了解海战
✅创作者：贤鱼
⏰预计时间：15分钟

@TOC

题目

小理最近痴迷于航海游戏，他发现了一个著名的经典海战游戏，准备大展身手。在这
个著名的游戏中，在一个方形的盘上放置了固定数量和形状的船只，每只船却不能碰到其
它的船。在这个题中，我们仅考虑船是方形的，所有的船只都是由图形组成的方形。编写
程序求出该棋盘上放置的船只的总数。
输入:
输入第一行由用空格隔开的两个整数 R 和 C 组成，这两个数分别表示游戏棋盘的行
数和列数。接下来的 R 行每行包含 C 个字符，每个字符可以为“#”，也可为“.”，“#”表
示船只的一部分，“.”表示水。
输出:
为每一个段落输出一行解。如果船的位置放得正确（即棋盘上只存在相互之间不能接
触的方形，如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相
互接触了）。就输出一段话“There are S ships.”,S 表示船只的数量。否则输出“Bad placement.”
对于 100%的数据有: 1<=R,C<=1000

样例输入:
6 8
.....#.#

.....

.....

.......#

......

..#...

样例输出:
There are 5 ships.

思路

第一眼看到这个题目，以为就是一个染色问题，但是题目中说了，==方形的船==
所以这就是这个题的难点
解决方法如下

我们记录下走过的所有点，然后记录下横纵坐标最大的点
用最大的点求出面积，并且和遍历的点比较
如果一样就是方形，不一样就输出bad placement.

理论成立下面来实现一下

AC代码

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int dx[5]={
    0,1,-1,0,0
};
int dy[5]={
    0,0,0,1,-1
};
struct node{
    int x,y;
};
int sum;//记录每次遍历个数
int vis[1001][1001];
char mapp[1001][1001];
int n,m;
int ans=0;
int mx,my;
int bfs(int x,int y){
queue<node> q;
mx=x,my=y;
q.push((node){x,y});
vis[x][y]=1;
while(!q.empty()){
    node w=q.front();
    q.pop();
    for(int i=1;i<=4;i++){
        int tx=dx[i]+w.x;
        int ty=dy[i]+w.y;
        if(tx<=0||ty<=0||tx>n||ty>m||mapp[tx][ty]=='.'||vis[tx][ty]) continue;//先判断出界，能不能走和走没走过
        if(tx>mx) mx=tx;
        if(ty>=my) my=ty;//记录最大数据
        vis[tx][ty]=1;
        mapp[tx][ty]='.';
        q.push((node){tx,ty});
        sum++;
    }
}
if(sum==(mx-x+1)*(my-y+1)) return 1;//比较
else return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mapp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mapp[i][j]=='#'){
                sum=1;//遍历一下，由于在搜索的时候会改地图，所以这样遍历可以
                if(bfs(i,j)){
                    ans++;
                }else{
                    cout<<"Bad placement.";
                    return 0;
                }
            }
        }
    }
    cout<<"There are "<<ans<<" ships.";
    
}