原题传送门
0.前言 依旧是一个简单的搜索训练呢...
1.算法 DFS或BFS均可（此处使用DFS）
2.思路
看见样例，依然还是一道简单的搜索题。
这道题在原先是 普及/提高- 的题，后来是不是因为太简单被调了
可以把这道题主要要完成的操作：
- 搜索+统计船的个数
- 判断是否有船相邻
其中第一个操作非常好完成。就是就是一个简单的搜索遍历。
但是第二个操作就有些难度。
这里需要运用到一些技巧（找规律）
通过找规律我们可以发现，当在相邻的4个方格中，有三个是“*”时，则船会相邻
因为只能出现一下这四种不合法的情况：
* * * * * . . *
* . . * * * * *
3.代码
#include<iostream>
#include<cstdio>
using namespace std;
inline void read(int &x){ //快读
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
int x,y;
char map[1001][1001]; //存图
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1}; //上下左右遍历的辅助数组
inline bool judge(int m,int n){ //判断是否有船相邻的情况
int cnt=0;
if(map[m][n]=='#') cnt++;
if(map[m+1][n]=='#') cnt++;
if(map[m][n+1]=='#') cnt++;
if(map[m+1][n+1]=='#') cnt++;
if(cnt==3) return false;
else return true;
}
inline void DFS(int p,int q){
map[p][q]='^'; //把与当前(即"#")节点标成一个统一的符号
//为了和原"#"区分（因为是同一艘船）
for(int i=1;i<=4;i++){
if(p+dx[i]<0||p+dx[i]>x+1||q+dy[i]<0||q+dy[i]>y+1) continue; //边界条件不要忘
if(map[p+dx[i]][q+dy[i]]=='#'){ //当前节点也是船的时候才能继续遍历
DFS(p+dx[i],q+dy[i]);
}
}
}
int ans;
int main(){
read(x);read(y);
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cin>>map[i][j];
}
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(judge(i,j)==false){
printf("Bad placement."); //注意句号qwq
return 0;
}
}
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(map[i][j]=='#'){ //只要有"#"，就有一艘船
ans++;
DFS(i,j); //把整艘船全部搜出来
}
}
}
printf("There are %d ships.",ans); //注意句号qwq
return 0;
}