假设是1号点到2和3。 那么我们可以枚举公共路径的位置。然后分叉。
然后就是一个01最短路预处理了。BFS即可。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e3+10; const int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; int n,m,vis[N][N][3],res=1e9; char g[N][N]; void bfs(int a,int k){ deque<pair<int,int> > q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j]-'0'==a) vis[i][j][k]=0,q.push_back({i,j}); while(q.size()){ int x=q.front().first,y=q.front().second; q.pop_front(); for(int i=0;i<4;i++){ int tx=x+dx[i],ty=y+dy[i]; if(tx<=0||ty<=0||tx>n||ty>m||g[tx][ty]=='#'||vis[tx][ty][k]<=1e6) continue; vis[tx][ty][k]=vis[x][y][k]+(g[tx][ty]=='.'); if(g[tx][ty]=='.') q.push_back({tx,ty}); else q.push_front({tx,ty}); } } } signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<3;k++) vis[i][j][k]=1e7; for(int i=1;i<=n;i++) scanf("%s",g[i]+1); bfs(1,0),bfs(2,1),bfs(3,2); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j]!='#') res=min(res,vis[i][j][0]+vis[i][j][1]+vis[i][j][2]-(g[i][j]=='.')*2); if(res>=1e7) res=-1; cout<<res; return 0; }