思路

这是一道蓝色的题（=水题）

题目要求在图中一点$ST$到某些点$IS[i]$再到一点$ED$的最短距离，显然是双向搜索，这里我采用的是双向bfs。我们用双向bfs预处理出从$ST$出发和从$ED$出发到各点的最短距离$d1[x][y]$和$d2[x][y]$，最后循环求$min(d1[is[i].x][is[]i].y+d2[is[i].x][is[]i].y)$即可。

这里还有一个注意点，即bfs的过程中可以通过$d[u.x][u.y]+1>=d[xx][yy]$判断是否多次经过进行剪支。

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
int ma[1005][1005],vis1[1005][1005],vis2[1005][1005];
int d1[1005][1005],d2[1005][1005];
int cnt;
struct node{
	int x,y;
}sta,to,is[1000005];
void bfs(){
	queue<node>q1,q2;
	q1.push(sta),q2.push(to);
	memset(d1,INF,sizeof(d1)); memset(d2,INF,sizeof(d2));
	d1[sta.x][sta.y]=0; vis1[sta.x][sta.y]=1;
	d2[to.x][to.y]=0; vis2[to.x][to.y]=1;
	while(!q1.empty()){
		node u=q1.front();q1.pop();
		for(int i=0;i<4;++i){
			int xx=u.x+dx[i],yy=u.y+dy[i];
			if(vis1[xx][yy]||xx<1||yy<1||xx>n||yy>m||ma[xx][yy]==1) continue;
			if(d1[u.x][u.y]+1>=d1[xx][yy])continue;
			vis1[xx][yy]=1;
			d1[xx][yy]=d1[u.x][u.y]+1;
			q1.push((node){xx,yy});
		}
	}
	while(!q2.empty()){
		node u=q2.front();q2.pop();
		for(int i=0;i<4;++i){
			int xx=u.x+dx[i],yy=u.y+dy[i];
			if(vis2[xx][yy]||xx<1||yy<1||xx>n||yy>m||ma[xx][yy]==1) continue;
			if(d2[u.x][u.y]+1>=d2[xx][yy])continue;
			vis2[xx][yy]=1;
			d2[xx][yy]=d2[u.x][u.y]+1;
			q2.push((node){xx,yy});
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&ma[i][j]);
			if(ma[i][j]==2)sta.x=i,sta.y=j;
			if(ma[i][j]==3)to.x=i,to.y=j;
			if(ma[i][j]==4)is[++cnt].x=i,is[cnt].y=j;
		}
	}
	bfs();
	int ans=INF;
	for(int i=1;i<=cnt;++i){
		ans=min(ans,d1[is[i].x][is[i].y]+d2[is[i].x][is[i].y]);
	}
	cout<<ans;
	return 0;
}

附

如果还想深入了解双端搜索可以去做做P4799世界冰球锦标赛和P3067Balanced Cow Subsets G（因为这道题有点easy了）