poj-3026

/664K79MSG++#include <cstdio>#include <cstring>#include <queue>using namespace std;#define LENGTH_MAX 54#define NODE_MAX 110#define WALL -1int maze[LENGTH_MAX][LENGTH_MAX]; // 0: nothing -1: wall >0: S or A's idint node_distance[NODE_MAX][NODE_MAX];struct Node {int x;int y;};typedef struct Node Node;Node nodes[NODE_MAX];int nodeNum;int mazeLength;int mazeWidth;struct BFSNode {int x;int y;int distance;};typedef struct BFSNode BFSNode;queue<BFSNode> BFSQueue;int BFSFlag[NODE_MAX][NODE_MAX];void processNode(int curX, int curY, int curDistance, int beginId) {BFSFlag[curX][curY] = 1;int upNodeId = maze[curX][curY];if (upNodeId > 0) { // Node in this (x,y)node_distance[beginId][upNodeId] = curDistance + 1; // get its shortest distance} else if (upNodeId == WALL) {return;}BFSNode upNode;upNode.x = curX;upNode.y = curY;upNode.distance = curDistance + 1;BFSQueue.push(upNode);}void BFS(int beginId) {while(BFSQueue.size()) {BFSQueue.pop();}memset(BFSFlag, 0, sizeof(BFSFlag));int beginX = nodes[beginId].x;int beginY = nodes[beginId].y;BFSNode beginNode;beginNode.x = beginX;beginNode.y = beginY;beginNode.distance = 0;BFSFlag[beginX][beginY] = 1;BFSQueue.push(beginNode);while(BFSQueue.size()) {BFSNode curNode = BFSQueue.front();BFSQueue.pop();int curX = curNode.x;int curY = curNode.y;int distance = curNode.distance;//upif ((curY-1>=0) && !BFSFlag[curX][curY-1]) { //if can upprocessNode(curX, curY-1, distance, beginId);}//Downif ((curY + 1 <= mazeWidth-1) && !BFSFlag[curX][curY+1]) {processNode(curX, curY+1, distance, beginId);}//leftif ((curX-1 >= 0) && !BFSFlag[curX-1][curY]) {processNode(curX-1, curY, distance, beginId);}//rightif ((curX + 1 <= mazeLength-1) && !BFSFlag[curX+1][curY]) {processNode(curX+1, curY, distance, beginId);}BFSFlag[curX][curY] = 2;}}void getNodeDistance() {for (int i = 1; i <= nodeNum; i++) {BFS(i);}// for (int i = 1; i <= nodeNum; i++) {// for (int j = 1; j <= nodeNum; j++) {// printf("%d -> %d: %d\n", i,j, node_distance[i][j]);// }// }}int key[NODE_MAX];char visited[NODE_MAX];#define INF 99999999void Prim() {int distanceSum = 0;for (int i = 1 ; i <= nodeNum; i++) {key[i] = INF;visited[i] = 0;}key[1] = 0;for (int i = 1; i <= nodeNum; i++) {int minId = -1;int minDistance = INF;for (int j = 1; j <= nodeNum; j++) {if (!visited[j] && minDistance > key[j]) { // get the shortest unprocessed node. minId = j;minDistance = key[j];}}visited[minId] = 1;// printf("%d %d\n", minId, minDistance);distanceSum += minDistance;for (int j = 1; j <= nodeNum; j++) {if (!visited[j] && node_distance[minId][j] > 0) { // check minId's adjanceyif (key[j] > node_distance[minId][j]) {key[j] = node_distance[minId][j];}}}}printf("%d\n", distanceSum);}void solve() {getNodeDistance();Prim();}int main() {int caseNum;char tmp[LENGTH_MAX] = "";// scanf("%d", &caseNum);gets(tmp);sscanf(tmp , "%d", &caseNum);for (int i = 0; i < caseNum; i++) {nodeNum = 0;memset(maze, 0, sizeof(maze));memset(node_distance, 0, sizeof(node_distance));memset(nodes, 0, sizeof(nodes));// scanf("%d %d", &mazeLength, &mazeWidth);char mazeline[LENGTH_MAX] = "";gets(mazeline);// printf("! %s", mazeline);sscanf(mazeline , "%d %d", &mazeLength, &mazeWidth);// printf("%d %d\n", mazeLength, mazeWidth);for (int i = 0; i < mazeWidth; i++) {memset(mazeline, 0, sizeof(mazeline));gets(mazeline);// printf("%s\n", mazeline);for (int j = 0; j < mazeLength; j++) {if (mazeline[j] == '#') {maze[i][j] = WALL;} else if (mazeline[j] == 'S' || mazeline[j] == 'A') {// printf("nodeNum %d %c\n", nodeNum, mazeline[j]);nodeNum++;maze[i][j] = nodeNum;nodes[nodeNum].x = i;nodes[nodeNum].y = j;}}}// printf("nodeNum %d\n", nodeNum);solve();}}

这是一个很好的综合问题，转化和综合难度适中.

第一次看问题可能不太容易理解问题的意思，但有一个关键点是在一开始搜索迷宫 或者 遇到alien时，团队可以分成几个搜索，

事实上，这秘密地解释了从任何一个 'A'/'S' 任何其他‘可以到达’A'/'S从S搜索开始， 它可以分为几个团队到任何其他数量的‘A'， 而在‘A在这里，团队也可以分裂到其他任何一个

的'A'/'S'， 题目还特别说明搜索团队大于100，保证即使再分裂所有alien(最多100)也能到达)

这样就可以了 'A'/'S看V， 而且每个V都是直接相互达到的(题目说明)，

结合主题要求的所有队列最终路径总长度的最小值实际上是每个V的最短路径，即最小生成树。

到了这里，就到了第一个考点，题目没有直接给出每一个‘’A'/'S相反，字符表示的迷宫分布图给出了距离。

这张图需要找出每V之间的(最短)距离，这个问题就变成了迷宫求最短路径(每两V之间的最短距离)。

迷宫的最短路径是BFS，这里如果按照简单的思维，就需要一一两点之间的最短距离，需要100*99次， 这样铁定TLE.

然而，由于使用BFS，您可以将两点的最短路径问题转化为迷宫的所有位置，以及与其他点的最短路径问题（因为所有其他点必须通过，必须是最短路径），因此每个点只需要一次BFS，最多只需要100次，以满足时间需求。(事实上，上述次数的计算并不严格，因为在这个问题中，边缘是无向的，要求A->B的最短距离 ，B->A的最短距离也可以得到，但即便如此，后者还是很有效率的)。

获得边缘权值后，直接Prim算法可以找到生成树的最小长度.