这道题卡了我 $40$ 多分钟。
其实就是跑两遍广搜，第一遍算出每个点距离树的最小距离，第二遍开个优先队列，算出逃回窝的途中最大可能的离它最近的树的距离的最小值。
接下来重点讲一下第二遍广搜。
首先，我们要知道，如果我们用 queue ，那么最先到的点不一定是最优的。
所以，我们需要用 priority_queue，来进行对下一层节点的扩展。
具体定义如下：
struct node{
int x,y,d;// d表示，离点{x,y}最近的树的距离的最小值
bool operator < (const node &tmp) const{
return d<tmp.d;
}//比较方式，距离大的先扩展
};
priority_queue<node> q1;
广搜部分就很简单了：
int ans=0x3f3f3f3f;
while(!q1.empty()){
st h=q1.top();
q1.pop();
if(h.x==edx&&h.y==edy){
ans=min(ans,h.d);
}
for(int i=0;i<4;i++){
int dx=h.x+dirx[i],dy=h.y+diry[i];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]){
vis[dx][dy]=1;
q1.push({dx,dy,min(h.d,cnt[dx][dy])});
}
}
}
总体代码如下（有人敢直接ctj吗）：
#include<bits/stdc++.h>
using namespace std;
#define reg register
int d[510][510];
char a[510][510];
int stx,sty,edx,edy;
queue<pair<int,int>> q;
int vis[510][510],cnt[510][510];
int dirx[4]={0,0,-1,1},diry[4]={1,-1,0,0};
int ans[510][510];
struct node{
int x,y,d;
bool operator < (const node &tmp) const{
return d<tmp.d;
}
};
priority_queue<node> q1;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='+')
{
q.push({i,j});
cnt[i][j]=0;
vis[i][j]=1;
}
if(a[i][j]=='V') stx=i,sty=j;
if(a[i][j]=='J') edx=i,edy=j;
}
}
while(!q.empty())
{
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int dx=x+dirx[i],dy=y+diry[i];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy])
{
cnt[dx][dy]=cnt[x][y]+1;
vis[dx][dy]=1;
q.push({dx,dy});
}
}
}
memset(vis,0,sizeof(vis));
q1.push({stx,sty,cnt[stx][sty]});
vis[stx][sty]=1;
int ans=0x3f3f3f3f;
while(!q1.empty()){
node g=q1.top();
q1.pop();
if(g.x==edx&&g.y==edy){
ans=min(ans,g.d);
}
for(int i=0;i<4;i++){
int dx=g.x+dirx[i],dy=g.y+diry[i];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]){
vis[dx][dy]=1;
q1.push({dx,dy,min(g.d,cnt[dx][dy])});
}
}
}
cout<<ans;
return 0;
}