自动搬运

查看原文

来自洛谷，原作者为

	ShaDouBuShi123 我是个人简介^_^

搬运于2025-08-24 21:18:27，当前版本为作者最后更新于2025-05-16 22:03:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：B4297 [蓝桥杯青少年组国赛 2022] 翻卡片

看到题，我们不禁会想到深度优先搜索的连通块问题。毕竟这是最简单基础的。

题目大意：

1. 输入一个 $n$，然后输入一个 $n×n$ 的矩阵。
2. 在这个矩阵里找到一个最佳的字母 B，使得将这张卡片上的字母换成 A 之后这一个区域的连通块面积最大。

先大致分析一下题目：

1. 输入一个 $n \times n$ 的矩阵，其中只包含大写字母 A 和 B。
2. 寻找一处个字母 B 的地方，将其改成 A。
3. 计算与这个字母连通的 A 的数量，完毕后将这个值与目前最大值比较，并实时更新最大值。
4. 重复过程 2，直到查找完毕。

这时候有的大佬就十分不屑：

不会爆时间吗？

不会！因为从数据范围可以看出，我们最多只需要重复 2500 次循环！

好的，这个问题已经解决了。先把深搜连通块问题的代码贴出来。

int dirx[4]={0,-1,0,1},diry[4]={1,0,-1,0};

void dfs(int x,int y)
{

	for (int i=0;i<4;i++)
	{
		int xx=x+dirx[i];//两个变量代表走之后的位置
		int yy=y+diry[i];
		if (xx>=0 && xx<n && yy>=0 && yy<m && G[xx][yy]==0)//越界处理+可否连通判断
		{
			G[x+dirx[i]][y+diry[i]]=1;//标记已经搜索过
			dfs(x+dirx[i],y+diry[i]);//搜索！
			//vis[x+dirx[i]][y+diry[i]]=0;
		}
	}
}

随便讲解一下这段代码。首先，这个函数传入的两个变量代表坐标，接下来一个循环循环四次，其功能是模拟。注意，深度优先搜索的特点是不撞南墙不回头，所以注意在写的时候不要出现无限递归。

等一下！这段代码并没有统计面积！不过没关系，我们只需要定义一个记录次数的全局变量就好了。

于是乎，把思路整合一下，我们得到了下面的代码：

#include <iostream>
#include <cstring>
using namespace std;

int G[105][105],vis[105][105]={},dirx[4]={0,-1,0,1},diry[4]={1,0,-1,0};
int n,m,maxn;
bool flag=false;
int sum=0;

void init()
{
    for (int k=0;k<n;k++)
    {
       	for (int l=0;l<m;l++)
       	{
         	vis[k][l]=0;
       	}
    }
}

void dfs(int x,int y)
{
    if (sum>maxn)
        maxn=sum;
    //vis[x][y]=1;
	for (int i=0;i<4;i++)
	{
		int xx=x+dirx[i];
		int yy=y+diry[i];
		if (xx>=0 && xx<n && yy>=0 && yy<m && G[xx][yy]==0 && vis[xx][yy]==0)
		{
			sum++;
			vis[x+dirx[i]][y+diry[i]]=1;
			dfs(x+dirx[i],y+diry[i]);
            //vis[x+dirx[i]][y+diry[i]]=0;
            //sum--;
		}
	}
}

int main()
{
	cin >> n;
    m=n;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
            char temp;
			cin >> temp;
            if (temp=='A')
                G[i][j]=0;
            else
                G[i][j]=1;
		}
	}

	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (G[i][j]==1)
			{
                G[i][j]=0;
				vis[i][j]=1;
                sum=0;
				dfs(i,j);
				G[i][j]=1;
				init();
			}
		}

	}
	cout << maxn+1;
	return 0;
}

（具体思路见上文）

然后提交上去就可以发现喜提 95 分。一看：读到 1，预期 0？由于我们在一开始没有算出发的格子，所以最后又把自己加了上去。可是万一没得翻呢？所以我们只需要再加一个特判，判断是否有 B 卡片出现过就可以了，非常简单，以下便是完整代码：

#include <iostream>
#include <cstring>
using namespace std;

int G[105][105],vis[105][105]={},dirx[4]={0,-1,0,1},diry[4]={1,0,-1,0};
int n,m,maxn;
bool flag=false,hasb=false;
int sum=0;

void init()
{
    for (int k=0;k<n;k++)
    {
       	for (int l=0;l<m;l++)
       	{
         	vis[k][l]=0;
       	}
    }
}

void dfs(int x,int y)
{
    if (sum>maxn)
        maxn=sum;
    //vis[x][y]=1;
	for (int i=0;i<4;i++)
	{
		int xx=x+dirx[i];
		int yy=y+diry[i];
		if (xx>=0 && xx<n && yy>=0 && yy<m && G[xx][yy]==0 && vis[xx][yy]==0)
		{
			sum++;
			vis[x+dirx[i]][y+diry[i]]=1;
			dfs(x+dirx[i],y+diry[i]);
            //vis[x+dirx[i]][y+diry[i]]=0;
            //sum--;
		}
	}
}

int main()
{
	cin >> n;
    m=n;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
            char temp;
			cin >> temp;
            if (temp=='A')
                G[i][j]=0;
            else
                G[i][j]=1;
		}
	}

	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (G[i][j]==1)
			{
                hasb=true;
                G[i][j]=0;
				vis[i][j]=1;
                sum=0;
				dfs(i,j);
				G[i][j]=1;
				init();
			}
		}

	}
    if (maxn==0&&!hasb)//新加入的部分
    {
        cout << 0;
        return 0;
    }
	cout << maxn+1;
	return 0;
}

以上就是这篇题解的全部内容，希望对大家有所帮助！