例题: P5198 [USACO19JAN]Icy Perimeter S
输入格式:
6
.##…
....#.
.#..#.
.#####
…###
....##
解题思路:
用dfs扫描每一个未访问的”#”,用path记录下一个连通块中的位置,面积就是path的大小。
遍历path,如果这个位置的上下左右超过了边界或者是”.”,那么周长++。代码如下
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
char g[N][N];
int st[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x,int y,vector<PII>& path)
{
st[x][y] = true;
path.push_back({x,y});
for(int i=0;i<4;i++)
{
int nx = x+dx[i],ny = y+dy[i];
if(nx < 1 || nx > n || ny < 1|| ny > n) continue;
if(st[nx][ny] || g[nx][ny] == '.') continue;
dfs(nx,ny,path);
}
}
int calc(vector<PII> path)
{
int sum = 0;
for(auto t : path)
{
int x = t.first,y=t.second;
for (int i = 0; i < 4; i ++ )
{
int nx = x+dx[i],ny = y+dy[i];
if(nx <= 0 || nx > n || ny <= 0|| ny > n || g[nx][ny]=='.') sum++;
}
}
return sum;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
}
}
int maxarea = 0,minc=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!st[i][j] && g[i][j] == '#')
{
vector<PII> path;
dfs(i,j,path);
int area = path.size();
int c = calc(path);
if(area > maxarea || (area == maxarea && c < minc))
{
maxarea = area,minc = c;
}
}
}
}
cout<<maxarea<<" "<<minc<<endl;
return 0;
}