洛谷 P5198 [USACO19JAN]Icy Perimeter S题解

题目：P5198 [USACO19JAN]Icy Perimeter S

题目大意：
给出一个由.和#组成的二维矩阵，每一个连通块都有一个面积和周长，求面积最大的连通块的面积和周长，若有多个面积一样大的，输出周长最小的那个。
解题思路：
根据题意，二维矩阵中最大的#连通块即为我们所求的面积，这个很好求，只要深搜或广搜。难点是理解周长的含义（不知道你有没有理解为什么案例的周长为22）。看下图（懒得画图了，来源题目的讨论区），这是我数的周长8+9=17。注意超出边界的地方也是我们要算的周长。

但实际上周长是这样的：

也就是说有的重复的.我们也要算。
代码：
DFS：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 1000;
const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, vis[maxn][maxn], map[maxn][maxn],area, perimeter, maxarea, maxperimeter;;
bool isValid(int x, int y) {
	if (x<1 || x>n || y<1 || y>n) {
		return false;
	}
	return true;
}

inline void DFS(int x, int y) {
	if (vis[x][y]||!isValid(x,y)||map[x][y]==0) {
		return;//这个点不是#、访问过、不合法就return.
	}
	vis[x][y] = 1;//标记点已经访问过
	area++;//计算面积
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (map[tx][ty] == 0) {
			perimeter++;//因为我把map转换为0,1表示，所以超出边界的地方map为0，可以算到超出边界的周长部分。
		}
		if(map[tx][ty]==1)
		{
			DFS(tx, ty);
		}
	}
}
int main() {
	char c;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> c;
			if (c == '#') {
				map[i][j] = 1;
			}
			else
			{
				map[i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 1 && !vis[i][j])
			{
				area = 0;
				perimeter = 0;
				DFS(i, j);
				if (maxarea < area)
				{
					maxarea = area;
					maxperimeter = perimeter;
				}
				else if (maxarea == area)
				{
					maxperimeter = min(maxperimeter, perimeter);
				}
			}
		}
	}
	cout << maxarea << " " << maxperimeter << endl;
}

BFS：

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct Node
{
	int x,y;
	Node() {

	}
	Node(int a, int b) {
		x = a;
		y = b;
	}
};
const int maxn = 1000;
const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, vis[maxn][maxn], map[maxn][maxn], area, perimeter, maxarea, maxperimeter;;
bool isValid(int x, int y) {
	if (x<1 || x>n || y<1 || y>n) {
		return false;
	}
	return true;
}
queue<Node>q;
void BFS(int x, int y) {
	q.push(Node(x, y));
	vis[x][y] = 1;
	while (!q.empty()) {
		Node temp = q.front();
		q.pop();
		area++;
		for (int i = 0; i < 4; i++) {
			int tx = temp.x + dx[i];
			int ty = temp.y + dy[i];
			if (map[tx][ty] == 0) {
				perimeter++;
			}
			if (map[tx][ty] == 1 && !vis[tx][ty]) {
				q.push(Node(tx, ty));
				vis[tx][ty] = 1;
			}
		}
	}
}
int main() {
	char c;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> c;
			if (c == '#') {
				map[i][j] = 1;
			}
			else
			{
				map[i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 1 && !vis[i][j])
			{
				area = 0;
				perimeter = 0;
				BFS(i, j);
				if (maxarea < area)
				{
					maxarea = area;
					maxperimeter = perimeter;
				}
				else if (maxarea == area)
				{
					maxperimeter = min(maxperimeter, perimeter);
				}
			}
		}
	}
	cout << maxarea << " " << maxperimeter << endl;
}