3026 Borg Maze

问题来自 poj 3026 Borg Maze

---

这道题其实就是求最小生成树。把所有A和S当做一个点，先BFS求出两两之间的最短距离建图，然后在图上找最小生成树。小心输入和数据范围。

---

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int N = 400;
const int M = 400;

char board[N][N];
int row, col;
int graph[M][M];
int numOfPoints;
int point[M][2];
int indices[N][N];
int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}};

void init()
{
    scanf("%d%d", &col, &row);
    memset(indices, 0xff, sizeof(indices));
    numOfPoints = 0;
    char c;
    while( (c = getchar()) != '\n')
        c = getchar();
    for(int r = 0; r < row; ++r)
    {
        gets(board[r]);
        for(int c = 0; c < col; ++c)
            if(board[r][c] == 'A' || board[r][c] == 'S')
            {
                indices[r][c] = numOfPoints;
                point[numOfPoints][0] = r;
                point[numOfPoints++][1] = c;
            }
    }
}

void bfs(int from, int r, int c)
{
    bool visited[N][N];
    memset(visited, false, sizeof(visited));
    visited[r][c] = true;
    int step = 1, found = 1;
    queue<pair<int, int> > tool;
    tool.push(pair<int, int>(r, c));
    while(!tool.empty() && found < numOfPoints)
    {
        int size = tool.size();
        while(size--)
        {
            pair<int, int> tmp = tool.front(); tool.pop();
            for(int d = 0; d < 4; ++d) 
            { 
                int tmpr = tmp.first+dir[d][0]; 
                int tmpc = tmp.second+dir[d][1]; 
                if(tmpr > 0 && tmpr < row && tmpc > 0 && tmpc < col && !visited[tmpr][tmpc] && board[tmpr][tmpc] != '#')
                {
                    visited[tmpr][tmpc] = true;
                    tool.push(pair<int, int>(tmpr, tmpc));
                    if(board[tmpr][tmpc] == 'A' || board[tmpr][tmpc] == 'S')
                    {
                        int to = indices[tmpr][tmpc];
                        graph[from][to] = graph[to][from] = step;
                        ++found;
                    }
                }
            }
        }
        ++step;
    }
}

int prim()
{
    int ret = 0;
    int dis[M];
    memset(dis, 0x3f, sizeof(dis));
    int count = 1;
    bool visited[M];
    memset(visited, false, sizeof(visited));
    visited[0] = true;
    for(int i = 1; i < numOfPoints; ++i)
        dis[i] = graph[0][i];
    while(count < numOfPoints)
    {
        int index = -1, mini = 0x3f3f3f3f;
        for(int i = 1; i < numOfPoints; ++i) 
            if(!visited[i] && mini > dis[i])
            {
                index = i;
                mini = dis[i];
            }
        visited[index] = true;
        ret += mini;
        ++count;
        for(int i = 1; i < numOfPoints; ++i)
            if(!visited[i] && graph[index][i] < dis[i])
                dis[i] = graph[index][i];
    }
    return ret;
}

int solve()
{
    memset(graph, 0x3f, sizeof(graph));
    for(int i = 0; i < numOfPoints; ++i)
        bfs(i, point[i][0], point[i][1]);
    return prim();
}

int main()
{
    int tcase;
    scanf("%d", &tcase);
    while(tcase--)
    {
        init();
        printf("%d\n", solve());
    }
    return 0;
}