审题本题需要我们找到最佳铺设道路将三个国家联通起来然后输出最佳铺设道路的铺设数量若没有联通方法则输出-1思路首先我们正面思考只需从某个点出发然后搜索到三个国家即可最后对比所有距离中最小的缺陷这种方法需要考虑的前提很多我们的国家不一定是连在一起的可能都分开可能其中两个国家连起来有可能都是直接连起来的所以不太好写代码正难则反我们可以从每个国家开始搜索搜索出三张铺设图然后根据这三张图的数据对每个非#点进行距离计算最后筛出最短铺设数并输出搜索方法01BFS由于铺设的时候遇到荒地可以铺设遇到国家的时候不用铺设所以对于铺设数的权值就是0和1.我们就可以采用01bfs了解题#includeiostream #includecstring #includedeque using namespace std; const int N 1010; typedef pairint, 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) { //清除痕迹 dequePII q; memset(dis[num], -1, sizeof dis[num]); //源点放入deque for (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; } } } //01bfs while (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 - 洛谷
算法题（176）：three states
审题本题需要我们找到最佳铺设道路将三个国家联通起来然后输出最佳铺设道路的铺设数量若没有联通方法则输出-1思路首先我们正面思考只需从某个点出发然后搜索到三个国家即可最后对比所有距离中最小的缺陷这种方法需要考虑的前提很多我们的国家不一定是连在一起的可能都分开可能其中两个国家连起来有可能都是直接连起来的所以不太好写代码正难则反我们可以从每个国家开始搜索搜索出三张铺设图然后根据这三张图的数据对每个非#点进行距离计算最后筛出最短铺设数并输出搜索方法01BFS由于铺设的时候遇到荒地可以铺设遇到国家的时候不用铺设所以对于铺设数的权值就是0和1.我们就可以采用01bfs了解题#includeiostream #includecstring #includedeque using namespace std; const int N 1010; typedef pairint, 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) { //清除痕迹 dequePII q; memset(dis[num], -1, sizeof dis[num]); //源点放入deque for (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; } } } //01bfs while (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 - 洛谷
