POJ 3026 Borg Maze (BFS+MST)

本文主要是介绍POJ 3026 Borg Maze (BFS+MST)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把是A或者S的地方当做一个顶点存起来。

之后用BFS求任意两点的距离，把边存起来用最小生成树算法求：使得所有顶点都连通的最小花费

/************************************************ Author: fisty* Created Time: 2015/2/28 16:42:55* File Name   : J.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define MAX_N 11000
int t,x,y,n;
int cnt;
char maze[55][55];
struct edge{int u;int v;int cost;
}G[MAX_N];
void addedge(int u, int v, int cost){G[cnt].u = u;G[cnt].v = v;G[cnt].cost = cost;cnt++;
}
bool cmp(edge e1, edge e2){return e1.cost < e2.cost;
}
int par[MAX_N];
void init(){for(int i = 0;i <= n; i++){par[i] = i;}
}
int find(int x){if(x == par[x]) return x;return par[x] = find(par[x]);
}
void unio(int x, int y){x = find(x);y = find(y);if(x != y){par[x] = y;}
}
int kurskal(){sort(G, G + cnt, cmp);int ans = 0;init();for(int i = 0;i < cnt; i++){edge e = G[i];if(find(e.u) != find(e.v)){unio(e.u, e.v);ans += e.cost;}}return ans;
}
struct Point{int x;int y;
}p[110];
int d[55][55];
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
void bfs(Point s){d[s.x][s.y] = 0;   queue<P> que;que.push(P(s.x, s.y));while(que.size()){P q = que.front(); que.pop();for(int i = 0;i < 4; i++){int _x = q.first + dx[i];int _y = q.second + dy[i];if(maze[_x][_y] != '#' && d[_x][_y] == INF && _x >= 0 && _x < x && _y < y && _y >= 0){d[_x][_y] = d[q.first][q.second] + 1;que.push(P(_x, _y));}}}       
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &t);while(t--){Memset(G, 0);Memset(maze, '\0');Memset(p, 0);n = 1;cnt = 0;scanf("%d%d", &y, &x);char g[MAX_N];gets(g);FOR(i, 0, x){FOR(j, 0, y){char c;scanf("%c", &c);if(c == ' ')maze[i][j] = '.';elsemaze[i][j] = c;if(maze[i][j] == 'A' || maze[i][j] == 'S'){p[n].x = i;p[n++].y = j;}}getchar();}n--;//Debug(n);for(int i = 1;i <= n; i++){Memset(d, 0x3f);bfs(p[i]);for(int j = 1;j <= n; j++){if(i != j){int cost = d[p[j].x][p[j].y];//Debug(i);//Debug(j);//Debug(cost);addedge(i, j, cost);}}}int ans = kurskal();printf("%d\n", ans);}return 0;
}

这篇关于POJ 3026 Borg Maze (BFS+MST)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---