審題：

本題需要我們找到最佳鋪設道路，將三個國家聯通起來，然后輸出最佳鋪設道路的鋪設數量，若沒有聯通方法則輸出-1

思路：

首先我們正面思考：只需從某個點出發然后搜索到三個國家即可，最后對比所有距離中最小的

缺陷：這種方法需要考慮的前提很多，我們的國家不一定是連在一起的，可能都分開，可能其中兩個國家連起來，有可能都是直接連起來的，所以不太好寫代碼

正難則反：我們可以從每個國家開始搜索，搜索出三張鋪設圖，然后根據這三張圖的數據對每個非#點進行距離計算，最后篩出最短鋪設數并輸出

搜索方法：01BFS

由于鋪設的時候遇到荒地可以鋪設，遇到國家的時候不用鋪設，所以對于鋪設數的權值就是0和1.我們就可以采用01bfs了

解題：
?

#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n, m;
char a[N][N];
int dis[4][N][N];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
void bfs(int num)
{//清除痕跡deque<PII> q;memset(dis[num], -1, sizeof dis[num]);//源點放入dequefor (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (num == a[i][j] - '0'){q.push_back({ i,j });dis[num][i][j] = 0;}}}//01bfswhile (q.size()){PII t = q.front(); q.pop_front();int x0 = t.first, y0 = t.second;for (int k = 0; k < 4; k++){int x = x0 + dx[k], y = y0 + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '#'){char next = a[x][y];int w = (next == '.' ? 1 : 0);if (dis[num][x][y] == -1)//首次遇到{dis[num][x][y] = dis[num][x0][y0] + w;if (w == 0) q.push_front({ x,y });else q.push_back({ x,y });}else if(dis[num][x0][y0] + w < dis[num][x][y])//松弛操作{dis[num][x][y] = dis[num][x0][y0] + w;}}}}
}
int main()
{//數據錄入cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}//搜索出三張鋪設圖bfs(1); bfs(2); bfs(3);//根據三張圖篩出結果并輸出int ret = 0x3f3f3f3f;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (a[i][j] == '#') continue;//石頭無法聯通int x = dis[1][i][j], y = dis[2][i][j], z = dis[3][i][j];if (x == -1 || y == -1 || z == -1) continue;//該點到達不了if (a[i][j] == '.')//減去重復鋪設的格子{ret = min(ret, x + y + z - 2);}else{ret = min(ret, x + y + z);}}}if (ret == 0x3f3f3f3f){cout << -1 << endl;}else{cout << ret << endl;}return 0;
}

注意：

1.最后在統計的時候遇到石頭是可以直接跳過的，而當距離中存在負數的時候說明有一個國家是無法到達的，此時也可以直接跳過

2.對于統計點為荒地的時候由于該地會被鋪設三次，所以我們需要減2，統計國家地塊的時候我們就直接加就行了，因為國家地塊是不會進行鋪設的，所以不存在重復鋪設的情況

CF590C Three States - 洛谷