题目链接：http://codeforces.com/contest/591/problem/E
题意：有3个数字表示3个城市，每种城市都是相互连通的，然后不同种的城市不一定联通，'.'表示可以建设道路‘#’表示
不能，问最短建设多少道路能够让3种城市都联通起来
题解：直接bfs一遍所有类型的城市，bfs的同时更新第i类城市到（x，y）点的最短距离，更新第i类城市到第j类城市的距离
具体看一下代码。
#include <iostream>
#include <cstring>
#include <queue>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 1e3 + 10;
char mmp[M][M];
int n , m , dr[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1};
int dis[4][M][M] , de[4][4];//dis表示i种城市到（x，y）点的最短距离初始值为inf，de表示第i个城市到第j个城市的最短距离初始值为inf
struct TnT {
int x , y;
TnT(){}
TnT(int x , int y):x(x) , y(y) {}
};
void bfs(int num) {
queue<TnT>q;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(mmp[i][j] == num + '0') {
q.push(TnT(i , j));
dis[num][i][j] = 0;
}
}
}
while(!q.empty()) {
TnT gg = q.front();
q.pop();
char cp = mmp[gg.x][gg.y];
if(cp != '.') {
de[num][cp - '0'] = min(dis[num][gg.x][gg.y] - 1 , de[num][cp - '0']);//更新第num种到其他两种城市的距离
}
for(int i = 0 ; i < 4 ; i++) {
TnT gl = gg;
gl.x += dr[i][0] , gl.y += dr[i][1];
if(gl.x >= 0 && gl.x < n && gl.y >= 0 && gl.y < m && mmp[gl.x][gl.y] != '#') {
if(dis[num][gl.x][gl.y] == inf) {
dis[num][gl.x][gl.y] = dis[num][gg.x][gg.y] + 1;//更新第num种城市到（x，y）点的距离，这里直接更新一次就行利用了bfs的特性，好好体会一下。
q.push(gl);
}
}
}
}
}
int main() {
cin >> n >> m;
for(int i = 0 ; i < n ; i++) {
cin >> mmp[i];
}
memset(dis , inf , sizeof(dis));
memset(de , inf , sizeof(de));
for(int i = 1 ; i <= 3 ; i++) {
bfs(i);//遍历3种城市
}
int ans = de[1][2] + de[1][3];
ans = min(de[1][2] + de[2][3] , ans);
ans = min(de[1][3] + de[2][3] , ans);
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(mmp[i][j] != '.') continue;
if(dis[1][i][j] == inf || dis[2][i][j] == inf || dis[3][i][j] == inf) continue;
ans = min(dis[1][i][j] + dis[2][i][j] + dis[3][i][j] - 2 , ans);
}
}
//ans总共的情况就是要么3种城市链接起来要么在中间找一个点算一下到3种城市的距离
if(ans >= inf) cout << -1 << endl;
else cout << ans << endl;
return 0;
}