原题链接：https://www.luogu.com.cn/problem/P1331

简单来说就是给出一个由‘#’和‘.‘组成的矩阵。需要识别存在几个矩形(被完全填充的)。如果有矩形相互衔接则认为出错。

那么如何识别矩形呢？关于矩形的思考有以下的三种：

1、对于r行c列的矩阵，1表示有效0表示无效。以行优先的方式遍历，如果在点(i,k)处出现一个1则进行以下操作：k不变递增i直到i为0作边界。获取第i行的长度len并遍历i+1以后有效的每一行，依次确定长度是否与len相等即可。实现的代码如下：

bool check(int x,int y)
{
int endx=x;
while(endx<r&&aim[endx][y])endx++;
//遍历行边界
int i=x;
int k=y;
while(k<c&&aim[i][k]){aim[i][k]=;k++;}
int endy = k;
//遍历第一行的列边界
for(i++;i<endx;i++)
{//控制行
for(k=y;k<c;k++)
{//控制列
if(!aim[i][k])break;
aim[i][k]=;
}
if(k!=endy)return false;
//注意是不等于
}
return true;
}

int solve()
{
int couts=;
for(int i=;i<r;i++)
{
for(int k=;k<c;k++)
{
if(aim[i][k])
{
if(check(i,k))couts++;
else return -;
}
}
}
return couts;
}

但是，有时候的情况并不允许，例如：(0->'.'&&1->'#')

该思路重视左边界与矩形内部，但是左边界往往不能够照应到整个连通区，所以方案不允许。

2、第二种方案是采用搜索的方式关注了矩形的坐标意义--即四个顶点的坐标关系。具体实现方式就是BFS遍历获取连通块的最极端的四个点后，再比较四个点的几何关系。具体代码如下：

struct point
{
int x,y;
};
int r,c;
int aim[][];
const int dx[]={,,,-};
const int dy[]={,-,,};
int tx[];
int ty[];

bool check(int x,int y)
{
queue psd;
point p;
p.x=x; p.y=y; psd.push(p);
int nowx,nowy;
while()
{
if(psd.empty())break;
p=psd.front();psd.pop();
nowx=p.x; nowy=p.y;
if(aim[nowx][nowy]==)continue;
aim[nowx][nowy]=;
//printf("(%d,%d)\n",nowx,nowy);
if(tx[]>=nowx&&ty[]>=nowy){tx[]=nowx;ty[]=nowy;}//左上角
if(tx[]>=nowx&&ty[]<=nowy){tx[]=nowx;ty[]=nowy;}//右上角 if(tx[]<=nowx&&ty[]>=nowy){tx[]=nowx;ty[]=nowy;}//左下角
if(tx[]<=nowx&&ty[]<=nowy){tx[]=nowx;ty[]=nowy;}//右下角 for(int i=;i<;i++) { int cx=nowx+dx[i]; int cy=nowy+dy[i]; if(cx>=&&cy>=&&cx<r&&cy<c&&aim[cx][cy])
{
p.x=cx;p.y=cy;psd.push(p);
}
}
}
/*for(int i=0;i<4;i++)
{
printf("tx[%d]=%d,ty[%d]=%d\n",i,tx[i],i,ty[i]);
}*/
bool ok;
ok=(ty[]==ty[])&&(ty[]==ty[]);
ok=ok&&(tx[]==tx[])&&(tx[]==tx[]);
return ok;
}

该方案仍然错误，因为对于任何一个矩形边框它都可以认为边框是合法的。也就是说该算法忽略了矩形的内部。

3、第二种方案其实基本上摸清了矩形的特征，只要解决“边框”问题就可以。也就是说要保证BFS遍历过的点数。其实只需要增加一个点数计数变量pointnum即可。BFS后直接根据四个顶点的坐标计算出应有的点的个数，比较即可。于是将上述代码更改如下：

#include
#include
#include
#include
using namespace std;
struct point
{
int x,y;
};
int r,c;
int aim[][];
const int dx[]={,,,-};
const int dy[]={,-,,};
int tx[];
int ty[];

bool check(int x,int y)
{
int pointnum=;
queue psd;
point p;
p.x=x; p.y=y; psd.push(p);
int nowx,nowy;
while()
{
if(psd.empty())break;
p=psd.front();psd.pop();
nowx=p.x; nowy=p.y;
if(aim[nowx][nowy]==)continue;
aim[nowx][nowy]=;
//printf("(%d,%d)\n",nowx,nowy);
pointnum++;
if(tx[]>=nowx&&ty[]>=nowy){tx[]=nowx;ty[]=nowy;}//左上角
if(tx[]>=nowx&&ty[]<=nowy){tx[]=nowx;ty[]=nowy;}//右上角 if(tx[]<=nowx&&ty[]>=nowy){tx[]=nowx;ty[]=nowy;}//左下角
if(tx[]<=nowx&&ty[]<=nowy){tx[]=nowx;ty[]=nowy;}//右下角 for(int i=;i<;i++) { int cx=nowx+dx[i]; int cy=nowy+dy[i]; if(cx>=&&cy>=&&cx%d\n",pointnum);
return ok;
}

int solve()
{
int couts=;
for(int i=;i<r;i++)
{
for(int k=;k<c;k++)
{
if(aim[i][k])
{
for(int p=;p<;p++)
{
tx[p]=i;ty[p]=k;
}
if(check(i,k))couts++;
else return -;
}
}
//printf("ok\n");
}
return couts;
}

int main()
{
//freopen("input.txt","r",stdin);
while(cin>>r>>c)
{
memset(aim,,sizeof(aim));
getchar();
for(int i=;i>m;
if(m=='#')aim[i][k]=;
}
getchar();
}
for(int i=;i<r;i++)
{
for(int k=;k<c;k++)
{
if(aim[i][k])printf("");
else printf("");
}
printf("\n");
}
printf("\n");
//
int num=solve();
if(num==-)printf("Bad placement.\n");
else printf("There are %d ships.\n",num);
/*for(int i=0;i<r;i++)
{
for(int k=0;k<c;k++)
{
if(aim[i][k])printf("%2d",1);
else printf(" ");
}
printf("\n");
}
printf("\n");*/
}
return ;
}

提交后完美解决。

#include
#include
#include
#include
using namespace std;
struct point
{
int x,y;
};
int r,c;
int aim[][];
const int dx[]={,,,-};
const int dy[]={,-,,};
int tx[];
int ty[];

bool check(int x,int y)
{
int pointnum=;
queue psd;
point p;
p.x=x; p.y=y; psd.push(p);
int nowx,nowy;
while()
{
if(psd.empty())break;
p=psd.front();psd.pop();
nowx=p.x; nowy=p.y;
if(aim[nowx][nowy]==)continue;
aim[nowx][nowy]=;
pointnum++;
if(tx[]>=nowx&&ty[]>=nowy){tx[]=nowx;ty[]=nowy;}//左上角
if(tx[]>=nowx&&ty[]<=nowy){tx[]=nowx;ty[]=nowy;}//右上角 if(tx[]<=nowx&&ty[]>=nowy){tx[]=nowx;ty[]=nowy;}//左下角
if(tx[]<=nowx&&ty[]<=nowy){tx[]=nowx;ty[]=nowy;}//右下角 for(int i=;i<;i++) { int cx=nowx+dx[i]; int cy=nowy+dy[i]; if(cx>=&&cy>=&&cx<r&&cy<c&&aim[cx][cy])
{
p.x=cx;p.y=cy;psd.push(p);
}
}
}
bool ok;
ok=(ty[]==ty[])&&(ty[]==ty[]);
ok=ok&&(tx[]==tx[])&&(tx[]==tx[]);
int s=(ty[]-ty[]+)*(tx[]-tx[]+);
ok=ok&&(s==pointnum);
return ok;
}

int solve()
{
int couts=;
for(int i=;i<r;i++)
{
for(int k=;k<c;k++)
{
if(aim[i][k])
{
for(int p=;p<;p++)
{
tx[p]=i;ty[p]=k;
}
if(check(i,k))couts++;
else return -;
}
}
}
return couts;
}

int main()
{
while(cin>>r>>c)
{
memset(aim,,sizeof(aim));
getchar();
for(int i=;i>m;
if(m=='#')aim[i][k]=;
}
getchar();
}
//
int num=solve();
if(num==-)printf("Bad placement.\n");
else printf("There are %d ships.\n",num);
}
return ;
}

提交的代码

OK