自动搬运

查看原文

来自洛谷，原作者为

	superballll **

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

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

以下是正文

题目分析

初读题时感觉太简单，看完数据范围发现自己太年轻，又感受到了被 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;
}