Three States

题意
有一个n*m的地图，地图上有三个国家和一些道路(路没修就不能走)，还有一些障碍，每个国家都是一个联通块，现在可以在道路上进行修路，让路可以走，现在问让三个国家联通最小需要修多少条路。

思路
对于每个国家都进行bfs，算出每个国家到每个点的最短距离。三个国家联通，枚举联通的一点即可。
所以枚举所有不是障碍的点，更新最小值，注意如果枚举的点是道路而不是国家的话，只需要有一个国家修路即可，所以要减去2.
bfs中，如果达到的坐标是"."，那么修路的就需要加1，保证bfs的最优性，如果是点，就把更新的坐标放到最后，如果是国家，不需要修路，花费保持不变，就丢到队列前，所以用一个双端队列实现。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
char mp[1005][1005];
int dis[4][1005][1005];
int to[][2]{1,0,-1,0,0,-1,0,1};
bool vis[1005][1005];
bool check(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m || mp[x][y]=='#' || vis[x][y]) return 1;
    return 0;
}
void bfs(int a){


    #define pa pair<int,int>
    #define x first
    #define y second
    deque<pa> que;
    memset(vis,0,sizeof vis);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]-'0'==a){
                que.push_back({i,j});
                dis[a][i][j]=0;
                vis[i][j]=1;
            }
        }
    }
    while(!que.empty()){
        pa now=que.front();
        que.pop_front();
        for(int i=0;i<4;i++){
            int fx=now.x+to[i][0],fy=now.y+to[i][1];
            if(check(fx,fy)) continue;
            vis[fx][fy]=1;
            int k=(mp[fx][fy]=='.');
            dis[a][fx][fy]=dis[a][now.x][now.y]+k;
            if(k) que.push_back({fx,fy});
            else que.push_front({fx,fy});
        }
    }

}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>mp[i];
    memset(dis,0x1f,sizeof dis);
    bfs(1),bfs(2),bfs(3);
    int ans=1e9;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]!='#'){
                int k=0;
                if(mp[i][j]=='.') k=2;
                ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]-k);
            }
        }
    }
    if(ans>=3*n*m) ans=-1;
    cout<<ans;
    return 0;
}