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

· · 题解

题目传送门

更好的阅读体验？

题目大意

给出一个 N \times N 的仅包含字母 A 或 B 的字符矩阵，每次可以将一个字母 B 改为字母 A，求翻转后相邻的字母 A 数量最多是多少。

思路分析

一道基础的搜索题。

由于题目数据范围很小，N \le 50，所以可以直接枚举每一个字母 B，将它改为字母 A，再使用广度优先搜索求相邻数量即可。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n,ans=0; //注意有可能一个 B 都没有，要初始化为一
int dh[5]={0,-1,0,1,0};
int dl[5]={0,0,1,0,-1};
bool f[60][60]; //标记数组，防止重复
char s[60][60];
int bfs(int x,int y){
    int sum=1; //相邻字母的数量
    memset(f,false,sizeof(f)); //初始化标记数组
    queue<int> qx,qy;
    qx.push(x);
    qy.push(y);
    f[x][y]=true;
    while(!qx.empty()){
        int h=qx.front(),l=qy.front();
        qx.pop();
        qy.pop();
        for(int i=1;i<=4;i++){
            int dx=h+dh[i],dy=l+dl[i];
            if(dx>=1 && dx<=n && dy>=1 && dy<=n){
                if(!f[dx][dy] && s[dx][dy]=='A'){
                    f[dx][dy]=true;
                    sum++; //数量加一
                    qx.push(dx);
                    qy.push(dy);
                }
            }
        }
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>s[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i][j]=='B'){ //枚举每一个字母 B
                ans=max(ans,bfs(i,j));
            }
        }
    }
    cout<<ans;
    return 0;
}