题目大意：有一个n*m的大陆，在大陆上有三个州（1、2、3），现在需要三个州相连，求最少需要修建多少个单元格作为道路。

题记：
首先要了解一下01BFS。bfs可以O（V+E）求解边权全为1的图上的最短路，但是当边权只有0或者1时，可以使用01BFS来快速求解。

01BFS维护一个双端队列，当边权为0时，是利用push_front()放在队头，边权为1时使用push_back()放在队尾。

以每个国家的任意一格为起点，对整张图跑一遍01BFS，就得到了三个国家到所有各自的距离。最后遍历所有各自，找到三个国家与这个格子的距离之和即是答案。

#include<bits/stdc++.h>

using namespace std;
#define int long long
typedef pair<int,int>PII;
#define F first
#define S second
const int N=1005;
const int INF=0x3f3f3f3f;
char a[N][N];
int dis[][2]={1,0,0,1,-1,0,0,-1};
int n,m;
int dist[N][N][4];
deque<PII>q;

bool check(int x,int y,int xx){
    if(x<1||x>n||y<1||y>m||a[x][y]=='#'||dist[x][y][xx]!=INF)
        return false;
    return true;
}

void bfs(int xx){

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==xx+'0'){
                dist[i][j][xx]=0;
                q.push_back(PII(i,j));
                //由于放进去的都是边权为0的点，所以放队头队尾都可以
            }
    //将x州的坐标全部放进队列
    while(!q.empty()){
        PII st=q.front();
        q.pop_front();
        //从队头拿出一个元素
        int x=st.F,y=st.S;
        for(int i=0;i<4;i++){
            int nx=x+dis[i][0];
            int ny=y+dis[i][1];
            if(check(nx,ny,xx)){
                int flag=a[nx][ny]=='.';
                //判断当前走到的这个格子是否为某一个州
                //两个不同州格子之间边权也为0
                dist[nx][ny][xx]=dist[x][y][xx]+flag;
                if(flag) q.push_back(PII(nx,ny));
                else q.push_front(PII(nx,ny));
            }
        }
    }
}

signed main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=3;k++)
                dist[i][j][k]=INF;
    //初始化三个州到每一格的距离都是无限大
    bfs(1);
    bfs(2);
    bfs(3);
    //bfs三个州
    int ans=INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int sum=dist[i][j][1]+dist[i][j][2]+dist[i][j][3];
            //cout<<sum<<endl;
            if(a[i][j]=='.')sum-=2;
            //由于a[i][j]这个点只需要铺一次道路,所以要减去两次
            ans=min(ans,sum);
        }
    }
    if(ans==INF) cout<<"-1"<<endl;
    else cout<<ans<<endl;
    return 0;
}