题意较为费解，仔细阅读理解题意，本题就是一个最小生成树问题，其中图的顶点是所有的alein和那个Borg，每两个顶点之间都有边连通，边的权重就是两个顶点间最小距离，这个最小距离可以用广度优先搜索算法（BFS）求出，最后用Prim算法求出最小生成树的长度即为答案。
注意：
（1）首先，注意输入x,y要用gets()来去末尾的空格。
（2）输入maze时，要用gets()，否则会接收不到空格。
（3）用BFS来将maze中噶字母变成转化成无向图，用邻接矩阵表示。
（4）用prim求最小生成树。
1
#include<iostream>
2#include<string>
3#include<limits>
4#include<queue>
5
6using namespace std;
7
8const int maxXY = 51;
9const int maxA = 102; //S当作A处理，故最大alien数为101
10
11const int INF = numeric_limits<int>::max();
12
13char maze[maxXY][maxXY];
14int mazeInt[maxXY][maxXY];
15int G[maxA][maxA];
16
17struct Point
18
{
19
int r; //row
20 int c; //column
21 int w;
22
};
23
24//BFS算法求Alien之间的距离
25void BFS(Point point,int x,int y)
26{
27
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
28
29 queue<Point> q;
30 Point cur,nex;
31
32 bool flag[maxXY][maxXY];
33
34 for(int i=0; i<y; i++)
35 {
36 for(int j=0; j<x; j++)
37 {
38 flag[i][j] = false;
39
}
40 }
41
42 point.w = 0;
43 flag[point.r][point.c] = true;
44 q.push(point);
45
46 while(!q.empty())
47 {
48 cur = q.front();
49 q.pop();
50
51 for(int i=0; i<4; i++)
52 {
53 nex.r = cur.r + dir[i][0];
54 nex.c = cur.c + dir[i][1];
55
56 int temp = mazeInt[nex.r][nex.c];
57
58 if((!flag[nex.r][nex.c]) && temp >= 0)
59 {
60
61 nex.w = cur.w + 1;
62 flag[nex.r][nex.c] = true;
63 q.push(nex);
64
65 if(temp > 0)
66 {
67 G[mazeInt[point.r][point.c]][temp] = nex.w;
68 }
69 }
70 }
71 }
72}
73
74//Prim算法求最小生成树
75int Prim(int n)
76{
77 int lowcost[maxA]; //到当前部分生成树的最小距离值
78 bool flag[maxA];
79
80 flag[1] = true;
81 for(int i=2; i<=n; i++)
82 {
83 lowcost[i] = G[1][i];
84 flag[i] = false;
85 }
86
87 for(int i=1; i<n; i++)
88 {
89 int temp = INF;
90 int v = 1;
91
92 //搜索下一条最短边加入生成树
93 for(int j=2; j<=n; j++)
94 {
95 if((!flag[j]) && (lowcost[j] < temp))
96 {
97 temp = lowcost[j];
98 v = j;
99 }
100 }
101 flag[v] = true;
102
103 //更新操作
104 for(int j=2; j<=n; j++)
105 {
106 if((!flag[j]) && (G[v][j] < lowcost[j]))
107 {
108 lowcost[j] = G[v][j];
109 }
110 }
111 }
112
113 int sumLen = 0;
114 for(int i=2; i<=n; i++)
115 {
116 sumLen += lowcost[i];
117 }
118
119 return sumLen;
120}
121
122
123int main()
124{
125 int N;
126 int x,y;
127 int nAlien;
128
129 char c[100];
130
131 Point point;
132
133 int i,j;
134
135 cin>>N;
136 while(N--)
137 {
138 cin>>x>>y;
139 gets_s(c);
140
141 for(i=0; i<y; i++)
142 {
143 gets_s(maze[i]);
144 }
145
146 //把符号迷宫转化为整数迷宫，对alien编号
147 nAlien = 0;
148 for(i=0; i<y; i++)
149 {
150 for(j=0; j<x; j++)
151 {
152 switch(maze[i][j])
153 {
154 case '#':
155 mazeInt[i][j] = -1;
156 break;
157
158 case ' ':
159 mazeInt[i][j] = 0;
160 break;
161
162 case 'A': //把S直接当A处理，但要注意maxA即就101了
163 case 'S':
164 mazeInt[i][j] = ++nAlien;
165 break;
166 }
167 }
168 }
169
170 //构造邻接矩阵
171 for(i=0; i<y; i++)
172 {
173 for(j=0; j<x; j++)
174 {
175 if(mazeInt[i][j] > 0)
176 {
177 point.r = i;
178 point.c = j;
179 BFS(point,x,y);
180 }
181 }
182 }
183
184 //求最小生成树
185 cout<<Prim(nAlien)<<endl;
186 }
187 return 0;
188}
189