POJ 3026 Brog Maze(BFS+Prim)

Description

将S和A所在点连成最小生成树

Analyze

用BFS求出(S、A)各点之间的最小距离，建立图的边

求最小生成树

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;

int n, m, node[N][N], num, dis[N][N], e[N * N][N * N], low[N * N];
char str[N], mp[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool vis[N][N], used[N * N];


void BFS(int x, int y)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));

    queue<P> q;
    q.push(P(x, y));
    vis[x][y] = 1;

    while(!q.empty())
    {
        P now = q.front();
        q.pop();

        int nowx = now.first;
        int nowy = now.second;
        if(node[nowx][nowy])
            e[ node[x][y] ][ node[nowx][nowy] ] = dis[nowx][nowy];
        for(int i = 0; i < 4; ++i)
        {
            int xx = nowx + dx[i];
            int yy = nowy + dy[i];
            if(xx >= 0 && xx < m && yy >= 0 && yy < n)
                if(!vis[xx][yy] && mp[xx][yy] != '#')
                {
                    q.push(P(xx, yy));
                    vis[xx][yy] = 1;
                    dis[xx][yy] = dis[nowx][nowy] + 1;
                }
        }
    }
}

void Prim()
{
    int ans = 0, mmin = INF, pos = 1;
    memset(used, 0, sizeof(used));

    ans += 0, used[pos] = 1;
    for(int i = 1; i <= num; ++i)
        low[i] = e[pos][i];

    int cnt = num;
    while(--cnt)
    {
        mmin = INF;
        for(int i = 1; i <= num; ++i)
            if(!used[i] && low[i] < mmin)
                mmin = low[i], pos = i;

        ///if(mmin == INF)

        ans += mmin, used[pos] = 1;
        for(int i = 1; i <= num; ++i)
            if(!used[i] && low[i] > e[pos][i])
                low[i] = e[pos][i];
    }
    cout << ans << '\n';
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d %d", &n, &m);

        num = 0;
        memset(e, 0, sizeof(e));
        memset(node, 0, sizeof(node));

        gets(str);
        for(int i = 0; i < m; ++i)
            gets(mp[i]);

        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(mp[i][j] == 'A' || mp[i][j] == 'S')
                    node[i][j] = ++num;

        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(node[i][j])
                    BFS(i, j);
        Prim();
    }
    return 0;
}