题解：P10294 [CCC 2024 J5] Harvest Waterloo

· · 题解

题目分析

初读题时感觉太简单，看完数据范围发现自己太年轻，又感受到了被 MLE 支配的压迫感！行和列的数据范围为 1\leq R\times C\leq 10^5 那也就是说当 R=1 或者 C=1 时，另外一条边都会达到最大值 10^5，那如果我们按这个数去开一个二维数组的话，就肯定喜提爆零了！那怎么办呢？

在标准模板库中有一个好东西，他不需要预先分配内存，这样不管 R 和 C 的值是多少，我们都不用担心 MLE 了！这就是动态数组 vector！整个对输入数据的处理过程，会让自己有一种在构建邻接表的错觉，但是在使用中，几乎是与二维数组一模一样！要是非说有什么不同，可能就是下标必须得从 0 开始吧，但是万幸的是：题目中的南瓜地下标就是从 0 开始的！

定义两个动态数组，一个是 p 表示这片南瓜地，类型为字符型；另一个是 vis 表示有没有来过，类型为布尔型。定义的程序如下：

vector<char>p[100005];
vector<bool>vis[100005];

然后就是根据输入去构造这两个动态数组，其中要注意第一行的字符我们要给 p[0][j] 因此 for 循环要从 0 开始。此外，还需要定义一个字符型变量用于临时记录输入的字符，然后填入动态数组 p 中，同时由于初始状态下的南瓜地都没有去过，因此 vis 中就无脑放 0 就可以了！构造过程的程序如下：

for(int i=0;i<r;i++)
    for(int j=0;j<c;j++){
        cin>>m;
        p[i].push_back(m);
        vis[i].push_back(0);
    }

下面就开始模拟摘南瓜的过程了，其实使用深搜和广搜都是可以的，我个人选择的是深搜。在开始搜索的过程中，要去看一下题目中给的起点是否合理，因为可能有一个大大的坑：就是给定的起点处会不会是稻草！但是好在题目中说了，游戏开始时，一个农民在其中一个南瓜的位置上，那也就是意味着不用对起点进行判定了，直接搜就可以了！

代码

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

int r,c,sx,sy,ans=0;
char m;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1}; 
vector<char>p[100005];
vector<bool>vis[100005];

void dfs(int x,int y)
{
    if(p[x][y]=='S') ans+=1;
    else if(p[x][y]=='M') ans+=5;
    else if(p[x][y]=='L') ans+=10;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<0||xx>=r||yy<0||yy>=c) continue; //出范围了
        if(p[xx][yy]=='*') continue; //干草走不了
        if(vis[xx][yy]==1) continue; //摘过了
        vis[xx][yy]=1;
        dfs(xx,yy);
    }
}

int main()
{
    cin>>r>>c;
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
        {
            cin>>m;
            p[i].push_back(m);
            vis[i].push_back(0);
        }
    cin>>sx>>sy;
    vis[sx][sy]=1;
    dfs(sx,sy);
    cout<<ans;
    return 0;
}