POJ 3026 Borg Maze

Description

Input

Output

Sample Input

2
6 5
##### 
#A#A##
# # A#
#S  ##
##### 
7 7
#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####  

Sample Output

8
11

最小生成树的题。字母间的最小生成树。

首先是找点并建图。找点的话就遍历图形node[i][j]表示图中mp[i][j]的位置储存的是第几个点，若没有则为0；

然后就是bfs求各个点之间的最短路径，最后prim求最小生成树。就是建图的时候很无语呀。这个题还有一个巨坑，就是列如6 5之后还有空格，必须读入字符串，我还是太年轻了=。=

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<limits.h>
using namespace std;
char mp[110][110];//存图
int dis[110][110];//储存的图中每个点的距离
int node[110][110];//储存第i,j的位置是第几个点
int low[110];
int visit[110][110];//bfs判重
int vis[110];
int t,n,m,num;
int dr[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
struct nod{
    int x,y;
    int step;
};
void bfs(int sx,int sy)
{
   memset(visit,0,sizeof(visit));
   nod st,ed;
   st.x=sx;
   st.y=sy;
   st.step=0;
   visit[sx][sy]=1;
   queue<nod>q;
   q.push(st);
   while(!q.empty())
   {
       st=q.front();
       q.pop();
       if(node[st.x][st.y]&&(st.x!=sx||st.y!=sy))
           dis[node[sx][sy]][node[st.x][st.y]]=st.step;
       for(int i=0;i<4;i++)
       {
           int xx=st.x+dr[i][0];
           int yy=st.y+dr[i][1];
           if(xx<0||xx>=n||yy<0||yy>=m)
               continue;
           if(mp[xx][yy]!='#'&&!visit[xx][yy])
           {
               visit[xx][yy]=1;
               ed.x=xx;
               ed.y=yy;
               ed.step=st.step+1;
               q.push(ed);
           }
       }
   }
}
void prim()
{
    int  ans=0,pos;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=num;i++)
       low[i]=dis[1][i];
    vis[1]=1;
    for(int i=1;i<=num;i++)
    {
        pos=-1;
        for(int j=1;j<=num;j++)
        {
            if(!vis[j]&&(pos==-1||low[pos]>low[j]))
                pos=j;
        }
        if(pos==-1)
            break;
        ans+=low[pos];
        vis[pos]=1;
        for(int j=1;j<=num;j++)
        {
            if(!vis[j]&&low[j]>dis[pos][j])
                low[j]=dis[pos][j];
        }
    }
    printf("%d\n",ans);
}
int main()
{
   char str[5];
   cin>>t;
   while(t--)
   {
       cin>>m>>n;
       gets(str);
       memset(node,0,sizeof(node));
       num=0;
       for(int i=0;i<n;i++)
       {
           gets(mp[i]);
           for(int j=0;j<m;j++)
           {
               if(mp[i][j]=='S'||mp[i][j]=='A')
               {
                  node[i][j]=++num;//表示是第几个点
//                  cout<<"i: "<<i<<"j: "<<j<<node[i][j]<<endl;
               }
           }
       }
       for(int i=0;i<n;i++)//遍历node中的每个点，求和其他点的最短路
       {
           for(int j=0;j<m;j++)
           {
               if(node[i][j])
                  bfs(i,j);
           }
       }
       prim();
   }
   return 0;
}

POJ 3026 Borg Maze,布布扣,bubuko.com

POJ 3026 Borg Maze

原文：http://blog.csdn.net/u013582254/article/details/38358743