未完善

lxy的通风报信

题目链接:https://ac.nowcoder.com/acm/contest/87255/G

题意:

在n * m网格种需要将军队合并并且求出最少多少天可以将军队合并
如果军队被挡则输出No

分析:

在一支军队移动时，其他军队不可移动。
由于只有一个军队在某一天可以移动，所以每次合并都必须依赖于一个'连接'操作，
即通过找到最短路径将两个不同军队连接起来 从这里可以看出需要使用最小生成树将
a个军队连接起来

我们需要计算从一个军队到所有其他军队的位置的最短路径长度 军队的移动是无权重的（即每步移动的代价相同），
BFS是一种适合的算法来计算这些最短路径。

最后得出思路:

如果要想将军队合并，就需要知道每个军队之间的距离，我们可以跑bfs来实现，
当知道每个点之间的距离之后我们跑一下最小生成树就可以知道最少多少天可以将军队合并了，
如果军队与军队之间被阻挡无法到达，则输出No。

Code:

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5; 
int dirs[5] = {-1, 0, 1, 0, -1}; // 为了节省空间
int n, m, x[N], y[N], dp[N][N], vis[N][N], it;
char a[N][N];   

bool check(int x, int y) { 
    return x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == -1 && a[x][y] != '#';
} 

void bfs(int id) { // bfs的是id 到其他军队的值
    queue<pair<int, int>> q;
    memset(vis, -1, sizeof(vis)); 
    q.push({x[id], y[id]});
    vis[x[id]][y[id]] = 0;   
    while (!q.empty()) {
        auto [x, y] = q.front();  
        q.pop(); 
        for (int i = 0; i < 4; i++) {  
            int dx = dirs[i] + x;
            int dy = dirs[i + 1] + y; 
            if (check(dx, dy)) { // 如果 (dx, dy)有效 
                q.push({dx, dy});
                vis[dx][dy] = vis[x][y] + 1; // 更新距离
            }
        }
    }  
    for (int i = 1; i <= it; i++) { // 计算每个军队到其他所有军队的距离
        if (vis[x[i]][y[i]] == -1) {
            cout << "No\n"; // 如果某个军队不可达，输出 "No"
            exit(0); // 直接结束程序
        }
        dp[id][i] = vis[x[i]][y[i]]; // 记录距离
    }
}

int f[N], ans;
vector<array<int, 3>> adj;   
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(15);  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];  
            if (a[i][j] == '*') {  
                x[++it] = i;
                y[it] = j;  
            }
        }
    }  
    for (int i = 1; i <= it; i++) { // 对每个军队执行 BFS 计算最短路径
        bfs(i);
    }  
    for (int i = 1; i <= it; i++) f[i] = i;  
    for (int i = 1; i <= it; i++) {
        for (int j = 1; j <= it; j++) {
            if (i != j) {  
                adj.push_back({dp[i][j], i, j});
            }
        }
    } 
    sort(adj.begin(), adj.end());   
    for (auto [w, x, y] : adj) { // 跑最小生成树 获得最少天数
        x = find(x), y = find(y);
        if (x != y) {
            ans += w;  
            f[y] = x;  
        }
    } 
    cout << ans;  
    return 0;
}