?

傳送門：Borg Maze

題意：有一個迷宮，里面有一些外星人，外星人用字母A表示，#表示墻，不能走，空格可以走，從S點出發，在起點S和A處可以分叉走，問找到所有的外星人的最短路徑是多少?

分析：分別bfs由S和所有A出發到其他點的距離，然后建好圖進行最小生成樹處理即可。

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 110 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; struct edge {int u,v,w;edge() {}edge(int u,int v,int w):u(u),v(v),w(w){}bool operator<(const edge &a)const{return w<a.w;} } e[N*N]; struct node {int x,y,step;node(){}node(int x,int y,int step):x(x),y(y),step(step){} }; int fa[N],tot,total; char str[N][N]; int num[N][N],vis[N][N],n,m; int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]); } int MST(int n) {int ans=0;for(int i=1;i<=n;i++)fa[i]=i;sort(e,e+tot);for(int i=0; i<tot; i++){int a=find(e[i].u);int b=find(e[i].v);if(a==b)continue;fa[a]=b;ans+=e[i].w;}return ans; } bool judge(int a,int b) {return a>=1&&a<=n&&b>=1&&b<=m&&str[a][b]!='#'&&!vis[a][b]; } void bfs(int x,int y) {queue<node>que;while(!que.empty())que.pop();FILL(vis,0);vis[x][y]=1;que.push(node(x,y,0));while(!que.empty()){node now=que.front();que.pop();for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++){if(i+j==0||i==j)continue;int a=now.x+i,b=now.y+j,step=now.step+1;if(judge(a,b)){if(str[a][b]=='A'||str[a][b]=='S'){e[tot++]=edge(num[x][y],num[a][b],step);}vis[a][b]=1;que.push(node(a,b,step));}}} } int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&m,&n);gets(str[0]);for(int i=1;i<=n;i++)gets(str[i]);total=0;tot=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(str[i][j]=='A'||str[i][j]=='S'){num[i][j]=++total;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(str[i][j]=='A'||str[i][j]=='S'){bfs(i,j);}}printf("%d\n",MST(total));} } View Code

?

轉載于:https://www.cnblogs.com/lienus/p/4277983.html

總結

以上是生活随笔為你收集整理的poj3206（bfs+最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。