该题题义是某个人从S点出发,去寻找所有的A,他可以直接到达每个A,也可以通过分身来到达,具体视那种方法所走的路程短而定。换句话说就是可以从A点再走到A点来寻找下一个A,而不选择再从S出发。
首先将任意两点之间(A或者S)的距离求出来(通过BFS)然后再建立最小生成树即可。注意输入数据中x,y后面不只一个空格。
代码如下:
#include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #define MAXN 105 using namespace std; int N, M, pos, pnum, set[MAXN]; int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; char G[55][55], hash[55][55]; struct Node { int x, y, dist; bool operator < (Node t) const { return dist < t.dist; } }e[MAXN*MAXN+5]; struct Point { int x, y; }p[MAXN]; struct Info { int x, y, step; }info; bool judge(int x, int y) { if (x >= 1 && x <= N && y >= 1 && y <= M) { return true; } else { return false; } } int bfs(int x) { memset(hash, 0, sizeof (hash)); struct Info obj; queue<Info>q; info.step = 0; info.x = p[x].x, info.y = p[x].y; q.push(info); while (!q.empty()) { obj = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int xx = obj.x+dir[i][0], yy = obj.y+dir[i][1]; if (judge(xx, yy) && !hash[xx][yy] && G[xx][yy] != -2) { if (G[xx][yy] != -1 && G[xx][yy] > x) { // 在这里建边 ++pos; e[pos].x = x, e[pos].y = G[xx][yy]; e[pos].dist = obj.step+1; } hash[xx][yy] = 1; info.x = xx, info.y = yy, info.step = obj.step+1; q.push(info); } } } } int find(int x) { return set[x] = x == set[x] ? x : find(set[x]); } void merge(int a, int b) { set[a] = b; } int main() { int T, length, cnt, ans; char cc; scanf("%d", &T); for (int t = 1; t <= T; ++t) { pos = pnum = cnt = ans = 0; scanf("%d %d", &M, &N); gets(G[0]); for (int i = 1; i <= N; ++i) { gets(G[i]+1); for (int j = 1; j <= M; ++j) { if (G[i][j] == 'S' || G[i][j] == 'A') { ++pnum; G[i][j] = pnum; // 直接将G图中的值赋为点的编号 p[pnum].x = i, p[pnum].y = j; } else if (G[i][j] == ' ') { G[i][j] = -1; // 由于‘#’和‘ ’的ascii码值与点的编号一样,一直WA } else if (G[i][j] == '#') { G[i][j] = -2; } } } for (int i = 1; i <= pnum; ++i) { set[i] = i; bfs(i); } sort(e+1, e+1+pos); for (int i = 1; i <= pos; ++i) { int a = find(e[i].x), b = find(e[i].y); if (a != b) { merge(a, b); ans += e[i].dist; ++cnt; if (cnt == pnum-1) { break; } } } printf("%d\n", ans); } return 0; }