为什么没有题解用优先队列，来个优先队列的。
先从起点 BFS 一遍，把到所有能到达灌木丛放入优先队列。
因为防止有些离终点近但不是最优的灌木丛更新答案。
再跑一遍优先队列 BFS 。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n, m, a[1002][1002], x1, y, sx, sy, f_x[4] = {1, -1, 0, 0}, f_y[4] = {0, 0, 1, -1}, t;
LL d[1000005][3],d1,d2,f1,f2;
bool b[1002][1002],u[1002][1002];
struct Node
{
int x,y,z;
Node(int x,int y,int z):x(x),y(y),z(z){}
bool operator <(Node a) const { return z < a.z; }
bool operator >(Node a) const { return z > a.z; }
};
priority_queue<Node, vector<Node>, greater<Node> > f;
//stl大法好
inline LL read(){
LL s=0,w=1;char ch;
ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*w;
}
void print(LL x){
char F[200];LL cnt=0;
if(x<0) {x=-x;putchar('-');}
if(x==0){putchar('0');putchar('\n');return ;}
while(x){F[++cnt]=x%10;x/=10;}
while(cnt){putchar(F[cnt--]+'0');}
putchar('\n');
return ;
}
int main(){
/*freopen("2.in", "r", stdin);
freopen("2.out", "w", stdout);*/
m = read(), n = read();
for (int i = 1; i <= n;i++){
for (int j = 1; j <= m;j++){
a[i][j] = read();
if(a[i][j]==2)
x1 = i, y = j;
}
}
d[d1][0]=(x1);
d[d1][1]=(y);
d[d1][2]=(0);
b[x1][y] = 1;
while(d1<=d2){//裸的bfs
x1 = d[d1][0];
y = d[d1][1];
t = d[d1][2];
for (int i = 0; i < 4;i++){
int xx = x1 + f_x[i], yy = y + f_y[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!b[xx][yy]&&a[xx][yy]!=3&&a[xx][yy]!=1){
d[++d2][0]=(xx);
d[d2][1]=(yy);
d[d2][2]=(t+1);
b[xx][yy] = 1;
if(a[xx][yy]==4){
//cout<<xx<<" "<<yy<<" "<<t+1<<endl;
f.push(Node(xx, yy, t + 1));//放到优先队列里
}
}
}
d1++;
}
while(!f.empty()){//第二次优先队列bfs
x1 = f.top().x;
y = f.top().y;
t = f.top().z;
if(a[x1][y]==3){//终点第一次取出时就是最优答案
print(t);
return 0;
}
for (int i = 0; i < 4;i++){
int xx = x1 + f_x[i], yy = y + f_y[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!u[xx][yy]&&a[xx][yy]!=1){
f.push(Node(xx,yy,t+1));
u[xx][yy] = 1;
}
}
f.pop();
}
return 0;
}
成功跑到 \(85ms\)。