#include<bits/stdc++.h>
using namespace std;
#define N 510
int h,w;char s[N][N];
int tsp,dfn[N][N];
bool is_tr[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct nd{int x,y;};
int dis(int x1,int y1,int x2,int y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
void solve()
{
	int stx,sty;cin>>stx>>sty;
	if(is_tr[stx][sty]){cout<<"0\n";return;}
	int ans=5e5+10;queue<nd>q;
	q.push({stx,sty});++tsp;
	while(q.size())
	{
		auto now=q.front();q.pop();
		int x=now.x,y=now.y;dfn[x][y]=tsp;
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>0&&xx<=h&&yy>0&&yy<=w&&dfn[xx][yy]!=tsp)
			{
				dfn[xx][yy]=tsp;
				int d=dis(stx,sty,xx,yy);
				if(d>=ans)continue;
				if(is_tr[xx][yy])ans=d;
				q.push({xx,yy});
			}
		}
	}
	is_tr[stx][sty]=1;cout<<ans<<'\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0); 
	cin>>h>>w;
	for(int i=1;i<=h;i++)
	{
		cin>>s[i]+1;
		for(int j=1;j<=w;j++)
			if(s[i][j]=='x')is_tr[i][j]=1;
	}
	int g;cin>>g;
	for(int i=1;i<=g;i++)solve();
	return 0;
}

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

考虑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;
}