2.Icy Perimeter
题目描述
Farmer John要开始他的冰激凌生意了！他制造了一台可以生产冰激凌球的机器，然而不幸的是形状不太规则，所以他现在希望优化一下这台机器，使其产出的冰激凌球的形状更加合理。
机器生产出的冰激凌的形状可以用一个N×N（1≤N≤1000）的矩形图案表示，例如：
每个’.‘字符表示空的区域，每个’#‘字符表示一块1×1的正方形格子大小的冰激凌。
不幸的是，机器当前工作得并不是很正常，可能会生产出多个互不相连的冰激凌球（上图中有两个）。一个冰激凌球是连通的，如果其中每个冰激凌的正方形格子都可以从这个冰激凌球中其他所有的冰激凌格子出发重复地前往东、南、西、北四个方向上相邻的冰激凌格子所到达。
Farmer John想要求出他的面积最大的冰激凌球的面积和周长。冰激凌球的面积就是这个冰激凌球中’#'的数量。如果有多个冰激凌球并列面积最大，他想要知道其中周长最小的冰激凌球的周长。在上图中，小的冰激凌球的面积为2，周长为6，大的冰激凌球的面积为13，周长为22。
注意一个冰激凌球可能在中间有“洞”（由冰激凌包围着的空的区域）。如果这样，洞的边界同样计入冰激凌球的周长。冰激凌球也可能出现在被其他冰激凌球包围的区域内，在这种情况下它们计为不同的冰激凌球。例如，以下这种情况包括一个面积为1的冰激凌球，被包围在一个面积为16的冰激凌球内：
同时求得冰激凌球的面积和周长十分重要，因为Farmer John最终想要最小化周长与面积的比值，他称这是他的冰激凌的“冰周率”。当这个比率较小的时候，冰激凌化得比较慢，因为此时冰激凌单位质量的表面积较小。
输入
输入的第一行包含N，以下N行描述了机器的生产结果。其中至少出现一个’#'字符。
输出
输出一行，包含两个空格分隔的整数，第一个数为最大的冰激凌球的面积，第二个数为它的周长。如果多个冰激凌球并列面积最大，输出其中周长最小的那一个的信息。
样例输入
6
##....
....#.
.#..#.
.#####
...###
....##
样例输出
13 22
正解
题意：找出一个冰激凌球，就是一个连通的地方，里面的点都可以到达这个冰激凌球的任何地方。这个冰激凌球的面积要大，在面积一样大时，比较谁的周长更小。最后输出面积最大同时周长更小的冰激凌球的面积和周长
解题思路：这题很明显是道搜索题，我用的是bfs。
枚举每一个点的位置，如果这个点没有被搜索过，并且是“#”，那就搜索它，将它这个冰激凌球找出来，求它的面积和周长，再按照题目规定进行比较，最后输出比较过后的面积和周长
找冰激凌球：用bfs去找就行了，套用模板
面积：整个冰激凌球的大小，就是这个冰激凌球里面“#”的个数，可以边找冰激凌球边求面积
周长：就是“#”四周是“.”或没有东西就+1，最后的结果就是周长，同样可以边找冰激凌球边求周长
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,s,c,ss,cc,head,tail,xx[1000005],yy[1000005],a[1005][1005],b[1005][1005];
int dx[5]={
0,0,0,1,-1};
int dy[5]={
0,1,-1,0,0};
char ch;
void bfs(int x,int y)//bfs 模板（修改了一点）
{
b[x][y]=1;
head=0;
tail=1;
xx[tail]=x;
yy[tail]=y;
while(head<tail)
{
head++;
for(int i=1;i<=4;i++)
{
int x1=dx[i]+xx[head],y1=dy[i]+yy[head];
if(x1>=0&&x1<=n+1&&y1>=0&&y1<=n+1)//边界条件有变化
if(b[x1][y1]==0)//没有被找过就进入循环
{
if(a[x1][y1]==0)c++;//如果找到了“.”就周长++
else
{
s++;//是“#”就面积++
tail++;//加入队列
xx[tail]=x1;
yy[tail]=y1;
b[x1][y1]=1;//标记
}
}
}
}
}
int main()
{
//freopen("perimeter.in","r",stdin);
//freopen("perimeter.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>ch;
if(ch=='#')a[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]==1&&b[i][j]==0)//如果是“#”且没有被搜索过就进入
{
s=1;//面积初始值（包括自己）
c=0;//周长初始值
bfs(i,j);//bfs搜索
if(s==ss&&c<cc)cc=c;//判断
if(s>ss){
ss=s;cc=c;}
}
cout<<ss<<' '<<cc;
return 0;
}
京公网安备 11010502036488号