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