J - Borg Maze——bfs+最小生成树_Prim算法

水深无声 2022-06-11 07:44 135阅读 0赞

Think:  
1知识点：bfs+最小生成树\_Prim算法  
2题意：最短路径和连接所有’A’和’S’结点  
3方法：对于每一个’A’和’S’结点通过bfs算法求出其与其它’A’和’S’结点的最短路径，建图，进而通过最小生成树\_Prim算法连接这tp个结点，使其构成连通图

[vjudge题目链接][vjudge]

以下为Accepted代码——63ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Node{
        int x;
        int y;
        int z;
    }link[144];
    
    int tp, n, m, co[104][104], e[144][144], book[104][104], vis[104], dis[104];
    char st[104][104];
    int jk[4][2]={
       {
       0,1},{
       1,0},{
       0,-1},{-1,0}};
    
    void bfs(int u, int v);
    bool Judge(int dx, int dy);
    void Prim();
    
    int main(){
        int T, i, j, cnt;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &m, &n);
            gets(st[0]);
            for(i = 0; i < n; i++){
                gets(st[i]);
            }
            cnt = 1, tp = 0;
            for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                    if(st[i][j] == 'A' || st[i][j] == 'S'){
                        co[i][j] = cnt++;
                        link[tp].x = i, link[tp].y = j, tp++;
                    }
                }
            }
            for(i = 0; i < tp; i++){
                int u = link[i].x;
                int v = link[i].y;
                bfs(u, v);
            }
            Prim();
        }
        return 0;
    }
    bool Judge(int dx, int dy){
        if(dx < 0 || dx >= n || dy < 0 || dy >= m)
            return false;
        else
            return true;
    }
    void bfs(int u, int v){
        int t1 = co[u][v];
        e[t1][t1] = 0;
        struct Node now, next;
        queue <struct Node> q;
        memset(book, 0, sizeof(book));
        now.x = u, now.y = v, now.z = 0;
        book[u][v] = 1;
        q.push(now);
        while(!q.empty()){
            now = q.front();
            q.pop();
            for(int i = 0; i < 4; i++){
                next.x = now.x + jk[i][0];
                next.y = now.y + jk[i][1];
                next.z = now.z + 1;
                if(Judge(next.x, next.y) && !book[next.x][next.y] && st[next.x][next.y] != '#'){
                    book[next.x][next.y] = 1;
                    q.push(next);
                    if(st[next.x][next.y] == 'A' || st[next.x][next.y] == 'S'){
                        int t2 = co[next.x][next.y];
                        e[t1][t2] = next.z;
                    }
                }
            }
        }
    }
    void Prim(){
        int i, miv, v, num, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= tp; i++)
            dis[i] = e[1][i];
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        while(num < tp){
            miv = inf;
            for(i = 1; i <= tp; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            vis[v] = 1, num++, sum += miv;
            for(i = 1; i <= tp; i++){
                if(!vis[i] && e[v][i] < dis[i])
                    dis[i] = e[v][i];
            }
        }
        printf("%d\n", sum);
    }

以下为Accepted代码——63ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Node{
        int x;
        int y;
        int z;
    }link[144];
    
    int tp, n, m, co[104][104], e[144][144], book[104][104], vis[104], dis[104];
    char st[104][104];
    int jk[4][2]={
       {
       0,1},{
       1,0},{
       0,-1},{-1,0}};
    
    void bfs(int u, int v);
    bool Judge(int dx, int dy);
    void Prim();
    
    int main(){
        int T, i, j, cnt;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &m, &n);
            gets(st[0]);
            for(i = 0; i < n; i++){
                gets(st[i]);
            }
            cnt = 1, tp = 0;
            for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                    if(st[i][j] == 'A' || st[i][j] == 'S'){
                        co[i][j] = cnt++;
                        link[tp].x = i, link[tp].y = j, tp++;
                    }
                }
            }
            for(i = 0; i < tp; i++){
                int u = link[i].x;
                int v = link[i].y;
                bfs(u, v);
            }
            Prim();
        }
        return 0;
    }
    bool Judge(int dx, int dy){
        if(dx < 0 || dx >= n || dy < 0 || dy >= m)
            return false;
        else
            return true;
    }
    void bfs(int u, int v){
        int t1 = co[u][v];
        int num = 1;
        e[t1][t1] = 0;
        struct Node now, next;
        queue <struct Node> q;
        memset(book, 0, sizeof(book));
        now.x = u, now.y = v, now.z = 0;
        book[u][v] = 1;
        q.push(now);
        while(!q.empty()){
            now = q.front();
            q.pop();
            for(int i = 0; i < 4; i++){
                next.x = now.x + jk[i][0];
                next.y = now.y + jk[i][1];
                next.z = now.z + 1;
                if(Judge(next.x, next.y) && !book[next.x][next.y] && st[next.x][next.y] != '#'){
                    book[next.x][next.y] = 1;
                    q.push(next);
                    if(st[next.x][next.y] == 'A' || st[next.x][next.y] == 'S'){
                        int t2 = co[next.x][next.y];
                        e[t1][t2] = next.z;
                        num++;
                    }
                    if(num == tp)
                        return;
                }
            }
        }
    }
    void Prim(){
        int i, miv, v, num, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= tp; i++)
            dis[i] = e[1][i];
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        while(num < tp){
            miv = inf;
            for(i = 1; i <= tp; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            vis[v] = 1, num++, sum += miv;
            for(i = 1; i <= tp; i++){
                if(!vis[i] && e[v][i] < dis[i])
                    dis[i] = e[v][i];
            }
        }
        printf("%d\n", sum);
    }

[vjudge]: https://vjudge.net/contest/163010#problem/J