🏆今日学习目标:
🍀学习了解sql注入漏洞
✅创作者:贤鱼
⏰预计时间:15分钟
🎉个人主页:贤鱼的个人主页
🔥专栏系列:c++
海战
- 题目
- 思路
- AC代码
题目
小理最近痴迷于航海游戏,他发现了一个著名的经典海战游戏,准备大展身手。在这
个著名的游戏中,在一个方形的盘上放置了固定数量和形状的船只,每只船却不能碰到其
它的船。在这个题中,我们仅考虑船是方形的,所有的船只都是由图形组成的方形。编写
程序求出该棋盘上放置的船只的总数。
输入:
输入第一行由用空格隔开的两个整数 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.";}