题解：B4286 [蓝桥杯青少年组省赛 2022] 农作物

· · 题解

这题典型的洪水填充。 （双倍经验在最后）

洪水填充主要思想：

  1. 对于每一个农作物，将这个农作物标记为杂草，防止死循环。
  2. 判断这个农作物上下左右是否为农作物，若是，则重复 1 操作。

即：

int dir[4][2]={0,1,1,0,-1,0,0,-1};//方向
void flood_fill(int x,int y)
{
    c[x][y]='X'; //1操作：标记为杂草
    for(int i=0;i<4;i++) //2操作：遍历其上下左右
    {
        int nx=dir[i][0]+x; 
        int ny=dir[i][1]+y;
        if(nx>0&&nx<=n&&ny>0&&ny<=m&&c[nx][ny]=='R')
            flood_fill(nx,ny); //若为农作物，则重复1操作。
    }
    return ;
}

我们可以遍历整个田地，若它为农作物，将其进行 1 操作。

即：

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(c[i][j]=='R')
        {
             flood_fill(i,j);
             ans++;
        }
    }    
}

代码

#include <iostream>
using namespace std;

char c[510][510];
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int n,m,ans;

void flood_fill(int x,int y)
{
    c[x][y]='X';
    for(int i=0;i<4;i++)
    {
        int nx=dir[i][0]+x;
        int ny=dir[i][1]+y;
        if(nx>0&&nx<=n&&ny>0&&ny<=m&&c[nx][ny]=='R')
            flood_fill(nx,ny);
    }
    return ;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(c[i][j]=='R')
            {
                flood_fill(i,j);
                ans++;
            }
        }    
    }
    cout<<ans;           
    return 0;
}

双倍经验：P1451 求细胞数量