自动搬运

查看原文

来自洛谷，原作者为

	Little_rock 吃饭不能抖腿是因为古代凳子不结实，晚上不能剪指甲是因为古代没有灯，床头不能对着窗户是因为古代没有窗帘。

搬运于2025-08-24 21:18:22，当前版本为作者最后更新于2025-04-02 20:50:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

洪水填充主要思想：

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 求细胞数量