传送门：点击打开链接
题意：在表格中，有3种site，每种site都是连通的，现在想让3种site连通，要在空地修路，求修最小的路使得3种site都连通。
思路：对于3种site，都求一遍BFS，记录每个点到每种site的最短距离。
途中顺便维护每种site之间的最短距离
那么最后答案会有2种情况，第一种情况是修的路是经过一个site的，这个只有3种情况，都讨论一下
还有一种情况是，一个空地修了路，这是到3种site的中间交汇点，枚举这个点，然后维护最小距离和即可
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1000 + 5;
const int INF = 0x3f3f3f3f;int n, m;
int d[3][MX][MX], dp[10][10];
char S[MX][MX];
int dist[][2] = {
{0, 1}, {0, -1}, {1, 0}, { -1, 0}};void build(int s) {queue<PII>Q;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(S[i][j] == '1' + s) {d[s][i][j] = 0;Q.push(PII(i, j));} else d[s][i][j] = INF;}}for(int i = 0; i <= 2; i++) {dp[s][i] = INF;}while(!Q.empty()) {PII f = Q.front();Q.pop();int x = f.first, y = f.second;if('1' <= S[x][y] && S[x][y] <= '3') {dp[s][S[x][y] - '1'] = min(dp[s][S[x][y] - '1'], d[s][x][y] - 1);}for(int k = 0; k < 4; k++) {int nx = x + dist[k][0], ny = y + dist[k][1];if(nx < 1 || nx > n || ny < 1 || ny > m || S[nx][ny] == '#') continue;if(d[s][nx][ny] == INF) {d[s][nx][ny] = d[s][x][y] + 1;Q.push(PII(nx, ny));}}}
}int main() { //FIN;while(~scanf("%d%d", &n, &m)) {for(int i = 1; i <= n; i++) {scanf("%s", S[i] + 1);}for(int i = 1; i <= 3; i++) {build(i - 1);}int ans = INF;ans = min(ans, dp[0][1] + dp[0][2]);ans = min(ans, dp[1][0] + dp[1][2]);ans = min(ans, dp[2][0] + dp[2][1]);for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(d[0][i][j] == INF || d[1][i][j] == INF || d[2][i][j] == INF) continue;ans = min(ans, d[0][i][j] + d[1][i][j] + d[2][i][j] - 2);}}printf("%d\n", ans == INF ? -1 : ans);}return 0;
}