解题思路
本题大致可分为以下两个部分:
-
预处理矩阵上的每一个点与所有树的最短曼哈顿距离。
-
计算出一条使每个点最近距离的最小值最大的最优路径。
这两个部分都可以使用 bfs
来求解。
对于第一部分,我们可以将所有树的位置信息丢进一个队列里,用 bfs
求出每一个点与树的最近的曼哈顿距离。
对于第二部分,我们可以使用优先队列搭配 bfs
,优先看那些目前最近距离比较大的点,当走过这个点后,算出在这个点之前的所有点与树的距离的最小值,再与当前的这个点与树的距离求出最小值。
ACcode:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=510;
struct node{int x,y,p;
};
struct di{int x,y,now;bool operator <(const di& i) const{return i.now>now;}
};
int n,m,sx,sy,ex,ey,mmin=1<<30;
queue<node>q;
priority_queue<di>p;
char ch[N][N];
int mp[N][N],idx[]={0,0,1,-1},idy[]={1,-1,0,0};
bool vis[N][N];
void bfs1(){while(!q.empty()){auto tmp=q.front();int x=tmp.x,y=tmp.y,p=tmp.p;q.pop();for(int i=0;i<4;i++){int xx=x+idx[i];int yy=y+idy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){vis[xx][yy]=true;mp[xx][yy]=p+1;q.push({xx,yy,mp[xx][yy]});}}}
}
void bfs2(){while(!p.empty()){auto tmp=p.top();p.pop();int x=tmp.x,y=tmp.y;if(x==ex&&y==ey){mmin=min(mmin,tmp.now);}for(int i=0;i<4;i++){int xx=x+idx[i];int yy=y+idy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){vis[xx][yy]=true;p.push({xx,yy,min(tmp.now,mp[xx][yy])});}}}
}
void solve() {cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>ch[i][j];if(ch[i][j]=='+'){vis[i][j]=true;q.push({i,j,0});}else if(ch[i][j]=='V') sx=i,sy=j;else if(ch[i][j]=='J') ex=i,ey=j;}bfs1();p.push({sx,sy,mp[sx][sy]});memset(vis,false,sizeof vis);bfs2();cout<<mmin<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int tt=1;//cin>>tt;while(tt--)solve();return 0;
}
over~