【题目来源】
【题目描述】
在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能碰到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形组成的方形。
求出该棋盘上放置的船只的总数。
【输入格式】
第一行为两个整数 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.
*/
【参考文献】