自动搬运

查看原文

来自洛谷，原作者为

	YyunSu **

搬运于2025-08-24 22:08:08，当前版本为作者最后更新于2019-09-14 20:27:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

哇塞，好激动，AC了一道蓝题

在学校听大佬说这是一道纯搜索，于是我屁颠屁颠的做了一晚上，

没做出来，还好有大佬为我指明道路

在此感谢贞白徐晟，不要管大佬的名字颜色

看见好多大佬用广搜做，但是本蒟蒻自认为此题深搜更简洁易懂

话不多说，贴代码

#include <iostream>
#include <cstdio>
using namespace std;
char a[1005][1005];
int vis[1005][1005];
int dir[4][2] = {0,1,0,-1,1,0,-1,0}//方向数组，大佬们应该都知道吧...
int n,step = 0,step1 = 0;
int mmp (int r1, int r2) //不用在意函数名，不是我改的...qwq
{
	int k = 0;
	for (int w = 0; w < 4; w++){
		int xx = r1 + dir[w][0];
		int yy = r2 + dir[w][1];
		if (a[xx][yy] == '.') k++;
	}
	return k; 
} //求出上下左右“.”的数量，分开写更直观吧
void dfs(int x,int y) {
	vis[x][y] = step;//标记数组存步数，其实存什么无所谓...
	for(int i = 0; i < 4; i++) {
		int xx = x + dir[i][0];// 求上下左右的横坐标
		int yy = y + dir[i][1];//这个就是纵坐标喽
		if(xx >= 1 && xx <= n && yy >= 1 && yy <= n && !vis[xx][yy] && a[xx][yy] == '#') { // 判断边界以及是否被访问过
			step++;//存此时搜出来的冰淇淋大小
			step1 += mmp (xx, yy);//算一次四周的“.”的个数
			dfs(xx,yy);//递归走起
		}
	}
}
int main()
{
	int maxn = -9999,maxn1 = -9999;//一个存最大的冰淇淋的大小，另一个是“.”
	cin >> n;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i <= n + 1; i++){
		a[0][i] = '.';
		a[n + 1][i] = '.';
		a[i][0] = '.';
		a[i][n + 1] = '.';
	}//灵魂代码，把周围的边界全部弄成"." 鸣谢徐大佬的提醒
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if (a[i][j] == '#'){
				step = 1;
				step1 = mmp (i, j);
				dfs(i,j);
				if(maxn < step) maxn = step, maxn1 = step1;//每出一个答案就要比一次，是不是最大
				if(maxn == step)
					if (maxn1 > step1) maxn1 = step1; //同理 同上
			}	
		}
	}
	cout << maxn << ' '<< maxn1 <<endl;
	return 0;//完美结束（So beautiful!!!）
}

看完了的老爷们点个赞再走啊~~~