题目传送门: POJ 3026

题目大概意思是#是墙，不能走，S是起点，A是目标点，要求从S出发走到所有点，路径不可交叉，然后求最小的路径和。

就是一个BFS+MST的题，自己BFS写的有问题，真是够糟糕的。。。

###Code

POJ 3025
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct pos{
	int x, y;
	int step;
} pos;
pos p[120];
char amap[120][120];
bool vis[120], visit[120][120];
long long n, x, y, k, ans, map[120][120], dist[120], num[120][120];
long long add[4][2] = {
    {-1, 0}, 
    {0, -1}, 
    {0, 1}, 
    {1, 0}
};

void bfs(pos k)
{
	int i, xx, yy, nx, ny, step;
	pos p;
	queue <pos> que;
	memset(visit, false, sizeof(visit));
	que.push(k);
	visit[k.x][k.y] = true;
	while(!que.empty())
	{
		p = que.front();
		que.pop();
		xx = p.x;
		yy = p.y;
		step = p.step + 1;
		for(i = 0; i < 4; i++)
		{
			nx = xx + add[i][0];
			ny = yy + add[i][1];
			if(nx < x && nx >= 0 && ny < y && ny >= 0 && !visit[nx][ny])
			{
				if(amap[nx][ny] == 'S' || amap[nx][ny] == 'A')
				{
					map[num[k.x][k.y]][num[nx][ny]] = map[num[nx][ny]][num[k.x][k.y]] = step;
					p.x = nx;
					p.y = ny;
					p.step = step;
					que.push(p);
					visit[nx][ny] = true;
				}
				if(amap[nx][ny] == ' ')
				{
					p.x = nx;
					p.y = ny;
					p.step = step;
					que.push(p);
					visit[nx][ny] = true;
				}
			}
		}
	}
}

void prim(long long u)
{
	long long i, j, min, tmp;
	for(i = 1; i <= k; i++)
	{
		dist[i] = map[u][i];
		vis[i] = false;
	}
	vis[u] = true;
	tmp = u;
	for(i = 1; i <= k; i++)
	{
		min = 0x7FFFFFFF;
		for(j = 1; j <= k; j++)
			if(!vis[j] && min > dist[j])
			{
				tmp = j;
				min = dist[j];
			}
		if(min != 0x7FFFFFFF)
			ans += min;
		vis[tmp] = true;
		for(j = 1; j <= k; j++)
			if(!vis[j] && dist[j] > map[tmp][j])
				dist[j] = map[tmp][j];
	}
	return;
}

int main()
{
	long long i, j;
	char tmp;
	scanf("%lld", &n);
	while(n--)
	{
		k = 1;
		tmp = ' ';
		scanf("%lld%lld", &x, &y);
		while(tmp != '\n')
			tmp = getchar();
		for(j = 1; j <= y; j++)
		{
			for(i = 1; i <= x; i++)
			{
				tmp = getchar();
				amap[i][j] = tmp;
				if(tmp == 'A' || tmp == 'S')
				{
					p[k].x = i;
					p[k].y = j;
					p[k].step = 0;
					num[i][j] = k;
					k++;
				}
			}
			getchar();
		}
		k--;
		for(i = 1; i <= k; i++)
			bfs(p[i]);
		ans = 0;
		prim(1);
		printf("%lld\n", ans);
	}
    return 0;
}