题目链接：点击打开链接
题意：
给你一个地图，地图中A代表外星人，S代表出发点，从S点出发，每遇到一个A点便可分裂成多个。
求把所有A都吃完需要多少步。
刚开始没读好题，我以为S点随时都能分裂，头疼了好一会。
思路：
其实A和S是一样的，本题的本质就是求连接A和S的最小生成树。无非麻烦的一点就是各个结点之间的权值。
这里采取的办法是，枚举每一个结点进行一遍BFS，求该结点到其他所有结点的距离，若距离小于初始值，则更新该距离。
这样最终得到的就是每两个结点之间的最短距离。
代码：
#include <iostream> #include <string> #include <string.h> #include <queue> #include<stdio.h> using namespace std; const int inf = 1 << 20; string *map; int dis[110][110], x, y, alien[51][51], edge[110][110], num; bool vis[51][51]; int Move[][2] = {0,-1,0,1,-1,0,1,0}; void bfs(int sx, int sy) { queue<pair<int,int> >q; pair<int,int>p; p.first = sx, p.second = sy; q.push(p); memset(vis,false,sizeof(vis)); vis[sx][sy] = true; memset(dis,0,sizeof(dis)); while(!q.empty()) { int xx = q.front().first; int yy = q.front().second; q.pop(); if(alien[xx][yy]) edge[ alien[sx][sy] ][ alien[xx][yy] ] = dis[xx][yy]; for(int i = 0;i < 4;i++) { int mx = xx + Move[i][0]; int my = yy + Move[i][1]; if(mx<0||my<0||mx>=y||my>=x) continue; if(vis[mx][my] || map[mx][my] == '#') continue; vis[mx][my] = true; dis[mx][my] = dis[xx][yy] + 1; p.first = mx, p.second = my; q.push(p); } } } int Prim() { int Dis[110]; bool book[110]; book[1] = true; int t = 1, point, sum = 0, Min; for(int i = 1;i <= num;i++) Dis[i] = inf, book[i] = false; for(int k = 2;k <= num;k++) { Min = inf; for(int i = 2;i <= num;i++) { if(!book[i] && Dis[i] > edge[t][i]) Dis[i] = edge[t][i]; if(!book[i] && Dis[i] < Min) { Min = Dis[i]; point = i; } } t = point; sum += Min; book[t] = true; } return sum; } int main() { int N; cin>>N; while(N--) { memset(alien,0,sizeof(alien)); num = 0; cin>>x>>y; string a; getline(cin,a); map = new string[y]; for(int i = 0;i < y;i++) { getline(cin,map[i]); for(int j = 0;j < x;j++) if(map[i][j]=='S'||map[i][j] == 'A') alien[i][j] = ++num; } for(int i = 0;i < y;i++) for(int j = 0;j < x;j++) if(alien[i][j]) bfs(i,j); cout<<Prim()<<endl; } return 0; }