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; }