poj 3026

Description

Input

Output

Sample Input

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

Sample Output

8
11

Source

Svenskt M?sterskap i Programmering/Norgesmesterskapet 2001

题目意思就是求从S点到所有A点的路径值。

AC代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;
int s,n,m;
char map[60][60];
int b[60][60];
int f[60][60];
int G[110][110];
struct Node{
    int x,y;
    int step;
}a[120];
queue <Node> qu;
void bfs(Node t){
    int x,y;
    memset(f,0,sizeof(f));
    while(!qu.empty())
        qu.pop();
    f[t.x][t.y]=1;
    x=map[t.x][t.y]-'0';
    qu.push(t);
    while(!qu.empty()){
        Node tmp=qu.front(); qu.pop();
        if(map[tmp.x][tmp.y]=='A' || map[tmp.x][tmp.y]=='S'){
            G[b[t.x][t.y]][b[tmp.x][tmp.y]]=tmp.step;
        }

        if(tmp.x+1<=n && !f[tmp.x+1][tmp.y] && map[tmp.x+1][tmp.y]!='#'){  //下
            Node tt=tmp; tt.x++; tt.step++;
            qu.push(tt); f[tt.x][tt.y]=1;
        }

        if(tmp.x-1>=1 && !f[tmp.x-1][tmp.y] && map[tmp.x-1][tmp.y]!='#'){  //上
            Node tt=tmp; tt.x--;  tt.step++;
            qu.push(tt); f[tt.x][tt.y]=1;
        }

        if(tmp.y+1<=m && !f[tmp.x][tmp.y+1] && map[tmp.x][tmp.y+1]!='#'){  //右
            Node tt=tmp; tt.y++;  tt.step++;
            qu.push(tt); f[tt.x][tt.y]=1;
        }

        if(tmp.y-1>=1 && !f[tmp.x][tmp.y-1] && map[tmp.x][tmp.y-1]!='#'){  //左
            Node tt=tmp; tt.y--;  tt.step++;
            qu.push(tt); f[tt.x][tt.y]=1;
        }
    }
}
int prim(int t){
    int sum=0;
    int vis[110],dis[110];
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=s;i++)
        dis[i]=999999;
    dis[t]=0;
    for(int i=1;i<=s;i++){
        int min=999999;
        int v;
        for(int i=1;i<=s;i++){
            if(!vis[i] && dis[i]<min){
                min=dis[i];
                v=i;
            }
        }
        sum+=min;
        vis[v]=1;
        for(int j=1;j<=s;j++){
            if(!vis[j] && dis[j] > G[v][j])
                dis[j]=G[v][j];
        }
    }
    return sum;
}
int main(){
    int T; cin>>T;
    while(T--){
        cin>>m>>n;
        gets(map[0]);       //吸收n后面的多余空格和\n
        s=0;
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++){
            gets(map[i]+1);
            //cout<<map[i]+1<<endl;
            for(int j=1;j<=m;j++){
                if(map[i][j]=='S' || map[i][j]=='A'){
                    Node tmp; tmp.x=i; tmp.y=j; tmp.step=0;
                    a[++s]=tmp;
                    b[i][j]=s;                        //标记 i j 是第s个点
                }
            }
        }

        for(int i=1;i<=s;i++){
            bfs(a[i]);            //从每个点出发找出路径长度
        }
        for(int i=1;i<=s;i++){
            if(map[a[i].x][a[i].y]=='S'){    //找到S点，从S点出发进行prim
                cout<<prim(i)<<endl;
                break;
            }
        }
    }
    return 0;
}

poj 3026,布布扣,bubuko.com

poj 3026

原文：http://blog.csdn.net/my_acm/article/details/38349807