题解：P10294 [CCC 2024 J5] Harvest Waterloo

Wy_x · 2024-04-02 19:17:05 · 题解

P10294 [CCC 2024 J5] Harvest Waterloo

My Blog

Solotion:

由题可知，所求的是农夫所在的一个南瓜组成的连通块，不妨使用广度优先搜索（BFS）解决。

具体方法是：当队列非空时，进行循环，每次取出队首，并尝试从该点向上下左右进行扩展，若可以扩展，则更新记录数组，累加总价值，将拓展到的点推入队列；反之，不进行操作。

记忆数组的作用是防止一个点重复被访问。

注意：在遍历开始时，应先判断起点，若是干草块，不操作；否则，统计总价值，将起点推入队列，更新记忆数组，开始广搜。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int fx[4]={0,0,1,-1};
const int fy[4]={1,-1,0,0};

int r,c;
char a[5005][5005];
int z[200];
bool vis[5005][5005];
int ans;

signed main()
{
    z['S']=1;
    z['M']=5;
    z['L']=10;
    cin>>r>>c;
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
        cin>>a[i][j];

    int x,y;
    cin>>x>>y;
    x++;
    y++;
    //输入是以 (0,0) 为左上角，改为 (1,1)
    //横纵坐标加一

    queue<pair<int,int>> q;
    if(a[x][y]!='*')//起始地有南瓜
    {
        q.push(make_pair(x,y));
        //推入队列，开始遍历
        vis[x][y]=1;
        ans+=z[a[x][y]];
    }

    while(q.size())//BFS
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        //取出队首，坐标 (x,y)
        for(int i=0;i<4;i++)
        {//(x,y) 向上下左右四个方向扩展
            int xx=x+fx[i];
            int yy=y+fy[i];

            if(xx<1||yy<1||xx>r||yy>c) continue;//越界
            if(a[xx][yy]=='*') continue;//不能走
            if(vis[xx][yy]) continue;//走到过

            vis[xx][yy]=1;//记录到过
            ans+=z[a[xx][yy]];//价值累加
            q.push(make_pair(xx,yy));
            //将该点推入队列
        }
    }
    cout<<ans;

    return 0;
}