首页 > 代码库 > POJ 3026：Borg Maze(BFS建图+prim+MST）

POJ 3026：Borg Maze(BFS建图+prim+MST）

2024-07-13 18:08:12   222人阅读

Borg Maze

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 8250 Accepted: 2762

Description

The Borg is an immensely powerful race of enhanced humanoids from the delta quadrant of the galaxy. The Borg collective is the term used to describe the group consciousness of the Borg civilization. Each Borg individual is linked to the collective by a sophisticated subspace network that insures each member is given constant supervision and guidance. 

Your task is to help the Borg (yes, really) by developing a program which helps the Borg to estimate the minimal cost of scanning a maze for the assimilation of aliens hiding in the maze, by moving in north, west, east, and south steps. The tricky thing is that the beginning of the search is conducted by a large group of over 100 individuals. Whenever an alien is assimilated, or at the beginning of the search, the group may split in two or more groups (but their consciousness is still collective.). The cost of searching a maze is definied as the total distance covered by all the groups involved in the search together. That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3.

Input

On the first line of input there is one integer, N <= 50, giving the number of test cases in the input. Each test case starts with a line containg two integers x, y such that 1 <= x,y <= 50. After this, y lines follow, each which x characters. For each character, a space `` ‘‘ stands for an open space, a hash mark ``#‘‘ stands for an obstructing wall, the capital letter ``A‘‘ stand for an alien, and the capital letter ``S‘‘ stands for the start of the search. The perimeter of the maze is always closed, i.e., there is no way to get out from the coordinate of the ``S‘‘. At most 100 aliens are present in the maze, and everyone is reachable.

Output

For every test case, output one line containing the minimal cost of a succesful search of the maze leaving no aliens alive.

Sample Input

2
6 5
##### 
#A#A##
# # A#
#S  ##
##### 
7 7
#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####

Sample Output

8
11


题意：给定一个迷宫，在一个迷宫内，建立一颗最小生成树连接所有点。（这些点即‘A’或‘S’)
题解：通过BFS找到‘S‘与每个’A‘之间的最短路径。然后prim 建立最小生成树。

犯了一个非常低级的错误。。

还有那恶心的空格。。。不看解题报告。。真想不出来。。



#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 200;
char str[maxn][maxn];//字符串图
int map[maxn][maxn];//记录各类字符
int dis[maxn][maxn];//距离字符之间的距离的图
int vist[maxn][maxn];//用于BFS中的标记数组
int dx[] = {-1, 0, 0, 1};//查找方向
int dy[] = {0, -1, 1, 0};
int cas, row, col;//案例个数， 行， 列
int dot;//记录A和S的个数，即树的结点数
int cnt;//用于BFS中的结束队列

struct Node
{
    int x, y;
    int step;//记录距离
} node[maxn];

void init()//数据的输入与初始化
{

    scanf("%d%d", &col, &row);
    char c[51];
    gets(c);//用于处理输入时多余的空格
    dot = 0;
    memset( node, 0, sizeof(node) );
    for(int i=0; i<row; i++)
    {
        gets(str[i]);
        for(int j=0; j<col; j++)
        {
            if( str[i][j]=='A' || str[i][j]=='S' )
            {
                dot++;
                map[i][j] = dot;
                node[dot].x = i;
                node[dot].y = j;
            }
            else if( str[i][j]==' ' )
                map[i][j] = 0;
            else if( str[i][j]=='#' )
                map[i][j] = -1;
        }
    }
}

bool judge(int a, int b)//用于判断是否过界，或者是否能查找下去
{
    if( a<0 || a>=row || b<0 || b>=col || vist[a][b]==1 || map[a][b]==-1 )
        return false;
    return true;
}

void bfs()//BFS查找与建立距离图
{
    Node temp, next;//用于记录临时队列元元素和下一个队列元素
    queue<Node>Q;
    memset( dis, 0, sizeof(dis) );

    for(int i=1; i<=dot; i++)//求出每个S或A到其他点的距离，并建立图。
    {
        while( !Q.empty() )  Q.pop();//将队列清理
        memset( vist, 0, sizeof(vist) );
        node[i].step = cnt = 0;
        vist[node[i].x][node[i].y] = 1;
        Q.push( node[i] );
        // printf("%d  %d\n", node[i].x, node[i].y);

        while( !Q.empty() )
        {
            temp = Q.front();
            Q.pop();
            int x = temp.x;
            int y = temp.y;
            //printf("%d   %d\n", x,y);
            if( map[x][y] != 0 && map[x][y] != -1 )
            {
                cnt++;
                dis[i][ map[x][y] ] = dis[ map[x][y] ][i] = temp.step;
                //printf("%d\n", dis[i][map[x][y]]);
                if( cnt==dot )break;
            }

            for(int j=0; j<4; j++)//四个方向
            {
                int xx = temp.x + dx[j];
                int yy = temp.y + dy[j];
                if( judge( xx, yy ) )
                {
                    next.x = xx;
                    next.y = yy;
                    next.step = temp.step + 1;
                    vist[xx][yy] = 1;
                    Q.push( next );
                }
            }
        }
    }
}

void prim()//prim算法
{
    int k;
    int min;
    int lowdis[maxn];//用于求最小距离
    int vis[maxn];//用于记录结点是否进入树内
    int ans = 0;//最后的结果

    memset( vis, 0, sizeof( vis ) );

    for(int i=1; i<=dot; i++)
        lowdis[i] = INF;
    lowdis[1] = 0;

    for(int i=1; i<=dot; i++)
    {
        min = INF;
        for(int j=1; j<=dot; j++)
        {
            if( !vis[j] && lowdis[j]<min )
            {
                k = j;
                min = lowdis[j];
            }
        }
        ans += min;
        vis[k] = 1;
        for(int j=1; j<=dot; j++)
        {
            if( !vis[j] && dis[k][j]<lowdis[j] )
                lowdis[j] = dis[k][j];
        }
    }
    printf("%d\n", ans);
}

int main()
{
    scanf("%d", &cas);
    while( cas-- )
    {
        init();
        bfs();
        prim();
    }

    return 0;
}






POJ 3026：Borg Maze(BFS建图+prim+MST）


联系
我们