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

· · 题解

题解：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;
}

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