题目链接：https://ac.nowcoder.com/acm/problem/111125
题目大意：有一个地图有1，2，3个阵营。现在要修建路让1，2，3可以连接起来。如果地图是'1','2','3'这个单元格不用花费。'#'：不可以修建， '.'：费用为1.现在问最小费用是多少？

思路：我们知道一定是在地图上一个格子上汇合。枚举这个格子。dis1+dis2+dis3。如果这个格子是'.'有两个阵营在这个单元多修建了需要-2。

dis：用01bfs就可以了。

#include<bits/stdc++.h>
using namespace std;

char s[1005][1005];
int vis[3][1005][1005], f[3][1005][1005];
int xx[4]={0, 1, -1, 0};
int yy[4]={1, 0, 0, -1};
int n, m;
struct node{
    int x, y, T;
};
deque<node> q;
void bfs(int pos){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(s[i][j]=='1'+pos){
                q.push_back(node{i, j, 0});
            }
        }
    }
    while(!q.empty()){
        node t=q.front(); q.pop_front();
        f[pos][t.x][t.y]=t.T;
        for(int k=0; k<4; k++){
            int x=t.x+xx[k], y=t.y+yy[k];
            if(x<=n&&x>=1&&y<=m&&y>=1&&!vis[pos][x][y]&&s[x][y]!='#'){
                vis[pos][x][y]=1;
                if(s[x][y]=='.'){
                    q.push_back(node{x, y, t.T+1});
                }
                else{
                    q.push_front(node{x, y, t.T});
                }
            }
        }
    }
}

int main(){

    scanf("%d%d", &n , &m);
    for(int i=1; i<=n; i++){
        scanf("%s", s[i]+1);
    }
    bfs(0); bfs(1); bfs(2);
    int ans=1<<30;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(s[i][j]=='#'||!vis[0][i][j]||!vis[1][i][j]||!vis[2][i][j]) continue;
            if(s[i][j]=='.'){
                ans=min(ans, f[0][i][j]+f[1][i][j]+f[2][i][j]-2);
            }
            else{
                ans=min(ans, f[0][i][j]+f[1][i][j]+f[2][i][j]);
            }
        }
    }
    if(ans==1<<30){
        printf("-1\n");
    }
    else{
        printf("%d\n", ans);
    }

    return 0;
}