思路

01bfs

维护 $3$ 个最短距离，d[0][i][j] 表示从外围走到 $(i,j)$ 的最短距离，d[1][i][j] 表示从第一个人走到 $(i,j)$ 的最短距离，d[2][i][j] 表示从第二个人走到 $(i,j)$ 的最短距离，最后 $ans=min(d[0][i][j]+d[1][i][j]+d[2][i][j])$。

有两个细节要注意:

1.如果 s[i][j]='#' ，三段距离重复计算了，需要减掉 2 ,即$(d[0][i][j]+d[1][i][j]+d[2][i][j]-2)$ 2. 可以直接从外围拯救这两个人，此时 $ans=min(ans,d[0][i][j]+d[0][i][j])$

课堂演示代码：

#include<bits/stdc++.h>
#define y1 yy1   //全局变量不能出现y1
using namespace std;
typedef long long ll;
int h,w,ans;
string s[105];
int x1,y1,x2,y2,num,d[3][105][105];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs1()//从四周走到(i,j)的最短距离 
{
	bool v[105][105]={0};
	deque<pair<int,int> >que;
	for(int j=0;j<=w+1;j++)
	{
		v[0][j]=v[h+1][j]=true;
		d[0][0][j]=d[0][h+1][j]=0;
		que.push_back({0,j});
		que.push_back({h+1,j});
	}
	for(int i=1;i<=h;i++)
	{
		v[i][0]=v[i][w+1]=true;
		d[0][i][0]=d[0][i][w+1]=0;
		que.push_back({i,0});
		que.push_back({i,w+1});
	}
	while(que.size())
	{
		int x=que.front().first,y=que.front().second; que.pop_front();
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||xx>h||yy<1||yy>w)continue;
			if(s[xx][yy]=='*'||v[xx][yy])continue;
			if(s[xx][yy]=='.'||s[xx][yy]=='$')
			{
				d[0][xx][yy]=d[0][x][y];
				v[xx][yy]=true;
				que.push_front({xx,yy});
			}
			if(s[xx][yy]=='#')
			{
				d[0][xx][yy]=d[0][x][y]+1;
				v[xx][yy]=true;
				que.push_back({xx,yy});
			}
		}
	}
}
void bfs2(int ss,int tt,int op)  //从（s,t）出发走到（i，j）的最短距离 
{
	bool v[105][105]={0};
	deque<pair<int,int> >que;
	d[op][ss][tt]=0; v[ss][tt]=true;
	que.push_back({ss,tt});
	while(que.size())
	{
		int x=que.front().first,y=que.front().second;
		que.pop_front();
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||xx>h||yy<1||yy>w)continue;
			if(s[xx][yy]=='*'||v[xx][yy])continue;
			
			if(s[xx][yy]=='.'||s[xx][yy]=='$')
			{
				d[op][xx][yy]=d[op][x][y];
				v[xx][yy]=true;
				que.push_front({xx,yy});
			}
			if(s[xx][yy]=='#')
			{
				d[op][xx][yy]=d[op][x][y]+1;
				v[xx][yy]=true;
				que.push_back({xx,yy});
			}
		}
		
	}
	
} 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>h>>w;
	for(int i=1;i<=h;i++)
	{
		cin>>s[i];
		s[i]='0'+s[i];
		for(int j=1;j<=w;j++)
			if(s[i][j]=='$')
			{
				++num;
				if(num==1)x1=i,y1=j;
				else x2=i,y2=j;
			}
	}
	memset(d,0x1f,sizeof(d));
	if(num==1)
	{
		bfs1();
		ans=h*w+1;
		ans=min(ans,d[0][x1][y1]);
		if(ans<h*w+1)cout<<ans;
		else cout<<"impossible";
	}
	else
	{
		bfs1();
		bfs2(x1,y1,1);
		bfs2(x2,y2,2);
		
		ans=h*w+1;
		
		for(int i=1;i<=h;i++)
			for(int j=1;j<=w;j++)
				if(s[i][j]=='.'||s[i][j]=='$')
					ans=min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]);
				else if(s[i][j]=='#')
					ans=min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]-2);
		ans=min(ans,d[0][x1][y1]+d[0][x2][y2]);
		
		if(ans<h*w+1)cout<<ans;
		else cout<<"impossible";
	}
	return 0;
}