NC24199. [USACO 2019 Jan S]Icy Perimeter
描述
机器生产出的冰激凌的形状可以用一个N×N（1≤N≤1000）的矩形图案表示，例如：
##.... ....#. .#..#. .##### ...### ....##
每个'.'字符表示空的区域，每个'#'字符表示一块1×1的正方形格子大小的冰激凌。
不幸的是，机器当前工作得并不是很正常，可能会生产出多个互不相连的冰激凌球（上图中有两个）。一个冰激凌球是连通的，如果其中每个冰激凌的正方形格子都可以从这个冰激凌球中其他所有的冰激凌格子出发重复地前往东、南、西、北四个方向上相邻的冰激凌格子所到达。
Farmer John想要求出他的面积最大的冰激凌球的面积和周长。冰激凌球的面积就是这个冰激凌球中'#'的数量。如果有多个冰激凌球并列面积最大，他想要知道其中周长最小的冰激凌球的周长。在上图中，小的冰激凌球的面积为2，周长为6，大的冰激凌球的面积为13，周长为22。
注意一个冰激凌球可能在中间有“洞”（由冰激凌包围着的空的区域）。如果这样，洞的边界同样计入冰激凌球的周长。冰激凌球也可能出现在被其他冰激凌球包围的区域内，在这种情况下它们计为不同的冰激凌球。例如，以下这种情况包括一个面积为1的冰激凌球，被包围在一个面积为16的冰激凌球内：
##### #...# #.#.# #...# #####
同时求得冰激凌球的面积和周长十分重要，因为Farmer John最终想要最小化周长与面积的比值，他称这是他的冰激凌的“冰周率”。当这个比率较小的时候，冰激凌化得比较慢，因为此时冰激凌单位质量的表面积较小。
输入描述
输入的第一行包含N，以下N行描述了机器的生产结果。其中至少出现一个'#'字符。
输出描述
输出一行，包含两个空格分隔的整数，第一个数为最大的冰激凌球的面积，第二个数为它的周长。如果多个冰激凌球并列面积最大，输出其中周长最小的那一个的信息。
示例1
输入:
6 ##.... ....#. .#..#. .##### ...### ....##
输出:
13 22
C++14(g++5.4) 解法, 执行用时: 79ms, 内存消耗: 49252K, 提交时间: 2020-09-07 22:31:24
#include<iostream>
#define HAND
const int MAXN=1e3+7;
const int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
int n,S,C,mxs,mic;//S是面积 C是周长
char ice[MAXN][MAXN];
bool vis[MAXN][MAXN];
void dfs(int x,int y) {
if(vis[x][y])
return ;
vis[x][y]=true;
S++;
for(int d=0; d<4; d++) {
int xx=x+dx[d],yy=y+dy[d];
if(xx<1||xx>n||yy<1||yy>n||ice[xx][yy]=='.')//注意周长条件处理
C++;
if(ice[xx][yy]=='#')
dfs(xx,yy);
}
return ;
}
void solve(void) {
std::cin>>n;
for(int i=1; i<=n; i++)
std::cin>>ice[i]+1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(ice[i][j]=='#'&&!vis[i][j]) {
S=C=0;
dfs(i,j);
if(S>mxs) {
mxs=S;
mic=C;
} else if(S==mxs)
mic=std::min(mic,C);
}
}
}
std::cout<<mxs<<' '<<mic;
}
int main(void) {
#ifdef HANDIN
freopen("perimeter.in","r",stdin);
freopen("perimeter.out","w",stdout);
#endif
solve();
return 0;
}
C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 105ms, 内存消耗: 56188K, 提交时间: 2022-11-08 13:49:41
#include <iostream>
using namespace std;
int n,ans=0,sum=0,imax=-1,iimax=-1,book[1010][1010],m[1010][1010];
char p[1010][1010];
int inext[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x,int y)
{
if(x<1||y<1||x>n||y>n||book[x][y]||p[x][y]=='.') return;
sum++;
book[x][y]=1;
for(int i=0; i<4; i++)
{
int tx=x+inext[i][0];
int ty=y+inext[i][1];
if(m[tx][ty]==0) ans++;
else dfs(tx,ty);
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cin >> p[i][j];
if(p[i][j]=='#') m[i][j]=1;
else m[i][j]=0;
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(m[i][j]&&!book[i][j])
{
ans=0,sum=0;
dfs(i,j);
if(imax<sum)
{
imax=sum;
iimax=ans;
}
else if(imax==sum)
{
iimax=min(ans,iimax);
}
}
}
}
cout << imax << ' ' << iimax ;
}
C++(clang++11) 解法, 执行用时: 40ms, 内存消耗: 34684K, 提交时间: 2021-01-21 21:49:41
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,ansc,anss,xx[]={1,-1,0,0},yy[]={0,0,1,-1},sums,sumc;
char a[1010][1010];
bool v[1010][1010];
void dfs(int x,int y){
v[x][y]=1;
sums++;
for(int i=0;i<4;i++){
int nx=x+xx[i],ny=y+yy[i];
if(v[nx][ny]) continue;
if(a[nx][ny]=='#') dfs(nx,ny);
else sumc++;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]=='#'&&!v[i][j]){
sums=0,sumc=0;
dfs(i,j);
if(sums>anss){
anss=sums;
ansc=sumc;
}
else if(sums==anss&&sumc<ansc) ansc=sumc;
}
}
}
cout<<anss<<' '<<ansc;
return 0;
}
pypy3(pypy3.6.1) 解法, 执行用时: 351ms, 内存消耗: 72388K, 提交时间: 2020-09-06 21:26:21
#!/usr/bin/env python3 # # Icy Perimeter # import sys, os from collections import deque def read_int(): return int(input()) def read_str(): return input().strip() n = read_int() s = [list(read_str()) for _ in range(n)] ans = (0, 0) for i in range(n): for j in range(n): if s[i][j] != '#': continue a = p = 0 q = deque([(i, j)]) s[i][j] = '*' while q: x, y = q.pop() a += 1 for ii, jj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]: if 0 <= ii < n and 0 <= jj < n: if s[ii][jj] == '#': s[ii][jj] = '*' q.append((ii, jj)) elif s[ii][jj] == '.': p += 1 else: p += 1 ans = max(ans, (a, -p)) print(ans[0], -ans[1])