自动搬运

查看原文

来自洛谷，原作者为

	max0810 刚刚上初一，正在学习数据结构，求大佬带

搬运于2025-08-24 22:31:58，当前版本为作者最后更新于2021-07-09 17:34:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路还是比较简单的，完全没有蓝题的难度。

考虑bfs，每遇到一个点就往外广度搜索，去找最近的点。

时间看起来比较多，但到了后面有很多树，每个点的时间是非常快的，再加点优化，时间其实差不多是O(g)的。

具体请见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
	int x,y;
}now,nex;
const int dir[4][2] = {0,-1,-1,0,0,1,1,0};
char a[505][505];
int r,s,g;
bool vis[505][505];
int f(int x1,int y1,int x2,int y2)//算距离 
{
	return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
int bfs(int x,int y)//bfs模板不用多讲吧 
{
	memset(vis,0,sizeof vis);
	queue<node> que;
	int ans = 0x7ffffff;
	now.x = x;now.y = y;
	que.push(now);
	while(!que.empty())
	{
		now = que.front();
		que.pop();
		if(f(now.x,now.y,x,y)>ans)continue;//比最小值大就没必要枚举下去了（优化） 
		for(int i = 0;i < 4;i++)
		{
			int xx = now.x+dir[i][0];
			int yy = now.y+dir[i][1];
			if(xx<1||xx>r||yy<1||yy>s||vis[xx][yy])continue;
			vis[xx][yy] = 1;
			int s = f(xx,yy,x,y);
			if(s >= ans)continue;//同上 
			if(a[xx][yy] == 'x')ans = s;//注意只有是当前位置有苹果树才更新答案 
			nex.x = xx;nex.y = yy;
			que.push(nex);
		}
	}
	return ans;
}
int main()
{
//	freopen("jabuke.in","r",stdin);
//	freopen("jabuke.out","w",stdout);
	cin >> r >> s;
	for(int i = 1;i <= r;i++)
		for(int j = 1;j <= s;j++)
			cin >> a[i][j];
	cin >> g;
	while(g--)
	{
		int x,y;
		cin >> x >> y;
		if(a[x][y] == 'x')//如果这个点是x就直接输出0（优化） 
		{
			cout << "0\n";
			continue;
		}
		cout << bfs(x,y) << endl;
		a[x][y] = 'x';//一定要记得 
	}
	return 0;
}