ACM UVA 10307 (Killing Aliens in Borg Maze)

题目： 

思路： (BFS and MST)

注意到题目中有这样一句话：
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.)。 

最开始只看到"split into two"， 结果走了不少弯路。让人想起高中老师一句话，“做题看到半截就开始做，你还做得安逸得很“。这在工作中也一样，做事一定要仔细，仔细可以弥补你的不足，仔细可以少犯很多不必要的错误。

言归正转，看到上面那句题意，我们就可以转换成，求最小生成树的问题。我们不用区分borg和alien，把它们都看作是图中的节点即可，先求每个节点之间的最短路径，然后使用Kruskal或者Prim算法生成MST即可。

代码：

//
// UVA 10307
//
// Author: xfye
// Status: AC
//
// First, find the shortest path between each node.
// Then, generate MST for these nodes and the weight
// of the MST is our result.
//

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

#define MAX_MAZE_WIDTH 51
#define MAX_ALIENS 100
// MAX_ALIENS and a start borg
#define MAX_NODES MAX_ALIENS + 1

#define INF 0x7fffffff

struct Position
{
    Position(int r, int c)
        : row(r),
          col(c)
    {
    }
    Position()
    {
        row = 0;
        col = 0;
    }
    int row;
    int col;
};

//
// maze information
//
char g_maze[MAX_MAZE_WIDTH][MAX_MAZE_WIDTH];
int g_mazeRows;
int g_mazeCols;
Position g_nodes[MAX_NODES];
int g_numNodes;

//
// g_nodes[i][j] is the length from node i to node j.
//
int g_weights[MAX_NODES][MAX_NODES];

//
// Use prim algorithm to generate MST for these nodes.
//
void generateMST()
{
    int visitedHT[MAX_NODES];
    int numLeftNodes = g_numNodes;

    memset(visitedHT, 0, sizeof(visitedHT));

    vector<int> connectedNodes;
    connectedNodes.push_back(0); // Select one node at first
    int numConnectedNodes = 1;
    int result = 0;
    visitedHT[0] = 1;

    while (numConnectedNodes < g_numNodes) {
        int nextNode = 0;
        int nextEdgeWeight = INF;
        for (int i = 0; i < connectedNodes.size(); i++) {
            int tmpWeight = INF;
            int tmpNode = 0;
            for (int k = 0; k < g_numNodes; k++) {
                if (g_weights[connectedNodes[i]][k] != 0 && !visitedHT[k]) {
                    if (tmpWeight > g_weights[connectedNodes[i]][k]) {
                        tmpWeight = g_weights[connectedNodes[i]][k];
                        tmpNode = k;
                    }
                }
            }
            if (nextEdgeWeight > tmpWeight) {
                nextEdgeWeight = tmpWeight;
                nextNode = tmpNode;
            }
        }

        connectedNodes.push_back(nextNode);
        visitedHT[nextNode] = 1;
        result += nextEdgeWeight;
        numConnectedNodes++;
    }

    cout << result << endl;
}

void doBFS(int nodeIndex)
{
    int visited[MAX_MAZE_WIDTH][MAX_MAZE_WIDTH];
    memset(visited, 0, sizeof(visited));

    int step = 0;
    queue<Position> queue1;
    queue<Position> queue2;
    queue1.push(g_nodes[nodeIndex]);
    visited[g_nodes[nodeIndex].row][g_nodes[nodeIndex].col] = 1;

    int numVisitedNodes = 1;
    queue<Position> *nextQueue = &queue1;
    while (!nextQueue->empty()) {
        queue<Position> *curQueue = nextQueue;
        if (nextQueue == &queue1) {
            nextQueue = &queue2;
        } else {
            nextQueue = &queue1;
        }
        step++;
        while (curQueue->size()) {
            Position pos = curQueue->front();
            curQueue->pop();

            //
            // Try to go the four directions
            //
            for (int i = 0; i < 4; i++) {
                Position nextPos = pos;
                nextPos.row += (i % 2) ? 0 : i - 1;
                nextPos.col += (i % 2) ? i - 2 : 0;
                if (nextPos.row >= 0
                    && nextPos.row + 1 < g_mazeRows
                    && nextPos.col >= 0
                    && nextPos.col + 1 < g_mazeCols
                    && g_maze[nextPos.row][nextPos.col] != '#'
                    && !visited[nextPos.row][nextPos.col]) {
                    nextQueue->push(nextPos);
                    if (g_maze[nextPos.row][nextPos.col] != ' ') {
                        // Meets a node
                        if (g_weights[nodeIndex][g_maze[nextPos.row][nextPos.col]] ==0
                            || g_weights[nodeIndex][g_maze[nextPos.row][nextPos.col]]> step) {
                            g_weights[nodeIndex][g_maze[nextPos.row][nextPos.col]] = step;
                        }
                    }
                    visited[nextPos.row][nextPos.col] = 1;
                }
            }
        }
    }
}

int main()
{
    int numCases;

    cin >> numCases;
    for (int i = 0; i < numCases; i++) {
        //
        // Reads maze information
        //
        cin >> g_mazeCols >> g_mazeRows;
        g_numNodes = 0;
        cin.ignore(1);
        for (int j = 0; j < g_mazeRows; j++) {
            cin.getline(g_maze[j], MAX_MAZE_WIDTH);
            for (int k = 0; k < g_mazeCols; k++) {
                switch (g_maze[j][k]) {
                case 'S':
                case 'A':
                    // Here, let g_maze[j][k] store the ID of the node.
                    g_maze[j][k] = g_numNodes;
                    g_nodes[g_numNodes].row = j;
                    g_nodes[g_numNodes].col = k;
                    g_numNodes++;
                    break;
                default:
                    break;
                }
            }
        }

        memset(g_weights, 0, sizeof(g_weights));

        //
        // Use BFS on each node to find all the shortest path between
        // each node.
        //
        for (int k = 0; k < g_numNodes; k++) {
            doBFS(k);
        }

        generateMST();
    }
}