problem

有一个的方格，每个格子上有3种情况：

1.障碍，不能通过
2.国家，有3种国家（标号为1,2,3）可以直接通过。
3.平地，可以花费1的代价建造一条道路。然后就可以直接通过了。

问最少需要在多少个平地上建立道路，使得3种国家之间两两连通。无法满足条件则输出-1

solution

三种国家肯定是在某个点相遇，那就枚举一下这个点，分别计算一下从每种国家到这个点的最小距离。三种国家的距离和就是在该点相遇的代价。

所以就对于每种国家跑一遍spfa，预处理出他到格子上每个点之间的最小距离。

需要注意的是，如果相遇点是平地，那么这个点就被3个国家都计算了一遍答案。所以将代价-2即可。

code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<ctime>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
char s[N][N];
int vis[N][N][4],n,m,dis[N][N][4];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define pi pair<int,int>
queue<pi>q;
void solve(int num) {
    int t = num - '0';
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            if(s[i][j] == num) {
                q.push(make_pair(i,j));
                vis[i][j][t] = 1;
                dis[i][j][t] = 0;
            }
        }
    }
    while(!q.empty()) {
        int x = q.front().first,y = q.front().second;q.pop();
        vis[x][y][t] = 0;
        for(int i = 0;i < 4;++i) {
            int X = x + dx[i],Y = y + dy[i];
            if(X < 1 || X > n || Y < 1 || Y > m || s[X][Y] == '#') continue;
            if(dis[X][Y][t] > dis[x][y][t] + (s[X][Y] == '.')) {
                dis[X][Y][t] = dis[x][y][t] + (s[X][Y] == '.');
                if(!vis[X][Y][t]) {
                    vis[X][Y][t] = 1;q.push(make_pair(X,Y));
                }
            }
        }
    }
}
int main() {
//    freopen("1.in","r",stdin);
    n = read(),m = read();
    memset(dis,0x3f,sizeof(dis));
    for(int i = 1;i <= n;++i)
        scanf("%s",s[i] + 1);

    for(int i = 1;i <= 3;++i) solve(i + '0');

    ll ans = 1e9;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            ll ret = 0;
//            printf("%d ",dis[i][j][3]);
            for(int k = 1;k <= 3;++k) {
                ret += dis[i][j][k];
            }
            ans = min(ans,ret - 2 * (s[i][j] == '.'));
        }
//        puts("");
    }
    if(ans > n * m) puts("-1");
    else cout<<ans;
    return 0;
}