洛谷 P1331：海战 ← Flood fill

【题目来源】 https://www.luogu.com.cn/problem/P1331 【题目描述】 在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能碰到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形组成的方形。 求出该棋盘上放置的船只的总数。 【输入格式】 第一行为两个整数 R 和 C，用空格隔开，分别表示游戏棋盘的行数和列数。 接下来 R 行，每行 C 个字符，为 # 或 .。# 表示船只的一部分，. 表示水。 【输出格式】 一行一个字符串，如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个 # 号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出 There are S ships.，S 表示船只的数量。否则输出 Bad placement.。 【输入样例一】

6 8
…..#.#
##…..#
##…..#
…….#
#……#
#..#…#

【输出样例一】 There are 5 ships.​​​​​​​ 【输入样例二】

6 6
…..#
##…#
##…#
..#..#
…..#
######

【输出样例二】 Bad placement. 【数据范围】 对于 100% 的数据，1≤R, C≤1000。 【算法分析】 ● 判断方法：若存在一个连通块不是方形（长方形或正方形），即若存在一个连通块的面积不等于它其中的 # 号的个数，就输出 Bad placement.。若所有连通块都是方形（长方形或正方形），则输出连通块的个数。 ● ​​​​​​​特别注意：本题的陈述，个人认为存在晦涩难懂的地方。故结合样例分析题意后，将本文陈述中的“方形”理解为“长方形或正方形”，而不是一堆网文中所说的“正方形”后，所编写的代码 AC。 【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+5;
char mp[N][N];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int n,m,ans;
int cnt; //number of #
int min_x,max_x,min_y,max_y;
bool flag=true;

void dfs(int x,int y) {
mp[x][y]='.';
cnt++;
min_x=min(min_x,x),max_x=max(max_x,x);
min_y=min(min_y,y),max_y=max(max_y,y);

for(int i=0; i<4; i++) {
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>=0 && tx<n && ty>=0 && ty<m && mp[tx][ty]=='#') {
dfs(tx,ty);
}
}
}

bool is_rectangle() {
int rect_area=(max_x-min_x+1)*(max_y-min_y+1);
if(cnt!=rect_area) return false;
/*for(int i=min_x; i<=max_x; i++) {
for(int j=min_y; j<=max_y; j++) {
if(mp[i][j]!='.') return false;
}
}*/
return true;
}

int main() {
cin>>n>>m;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin>>mp[i][j];
}
}

for(int i=0; i<n && flag; i++) {
for(int j=0; j<m && flag; j++) {
if(mp[i][j]=='#') {
cnt=0;
min_x=max_x=i;
min_y=max_y=j;
dfs(i,j);
ans++;
if(!is_rectangle()) {
flag=false;
break;
}
}
}
}

if(flag) printf("There are %d ships.",ans);
else printf("Bad placement.");

return 0;
}

/*
in:
6 8
…..#.#
##…..#
##…..#
…….#
#……#
#..#…#

out:
There are 5 ships.
*/

【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/118642238 https://www.cnblogs.com/-pwl/p/13647612.html https://www.luogu.com.cn/problem/solution/P1331 https://www.shuzhiduo.com/A/gAJGErp0dZ/