POJ 3206 最小生成樹，poj3206生成樹

POJ 3206 最小生成樹，poj3206生成樹

DESCRIPTION:
T_T 在下是讀不懂題意的。但是捏。現在知道是求把所有的點（是字母的點）連起來的最小的權值。即最小生成樹。因為求最小生成樹是不計較源點是哪個的。所以可以把A和S看成一樣的。首先需要用BFS廣搜算法求出任意兩點之間的最短距離。然後直接用prim或kruskal算法模板就歐克了。但是捏。貌似這道題有兩大坑。NO.1 輸入row 和 col 兩個數之後會有多余的空格。所以需要吃掉一個字符串而不是一個字符。NO.2 雖然題目說最多有100個外星人+1個源點。但是好像有102個點。這樣的話。數組必須開到>= 102。

23333333....雖然只有這兩個坑，但是bfs很混亂的我確實WA了一天多。

附bfs+prim代碼。

#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
using namespace std;

const int inf=2501;

char map[51][51];
int node[51][51];
int num;
int edge[102][102];
int x, y;

void bfs(int ii, int jj)
{
    /***initial***/
    int dist[55][55];
    int que_x[2500], que_y[2500];
    int head, tail;
    int move[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
    int vis[55][55];
     memset(vis, 0, sizeof(vis));
     head = 0;
     tail = 0;
     memset(dist, 0, sizeof(dist));

     que_x[tail] = ii;
     que_y[tail++] = jj;
     vis[ii][jj] = 1;

     while(head < tail)
     {
         int top_x = que_x[head];
         int top_y = que_y[head++];
         if (node[top_x][top_y])
         edge[node[ii][jj]][node[top_x][top_y]] = dist[top_x][top_y];
         for (int k=0; k<4; ++k)
         {
             int next_x = top_x + move[k][0];
             int next_y = top_y + move[k][1];
            if (next_x >= 0 && next_x < y && next_y >= 0 && next_y < x && !vis[next_x][next_y] && map[next_x][next_y] != '#')
             {
                vis[next_x][next_y] = 1;
                dist[next_x][next_y] = dist[top_x][top_y] + 1;
                que_x[tail] = next_x;
                que_y[tail++] = next_y;
             }
         }
     }
     return;
}

int prim(void)
{
    int s=1;
    int m=1;
    bool u[102];
    u[s]=true;

    int min_w;
    int prim_w=0;
    int point;
    int low_dis[102];

    for(int i=1;i<=num;i++)
    {
        low_dis[i]=inf;
        u[i]=false;
    }

    while(true)
    {
        if(m==num)
            break;

        min_w=inf;
        for(int i=2;i<=num;i++)
        {
            if(!u[i] && low_dis[i]>edge[s][i])
                low_dis[i] = edge[s][i];
            if(!u[i] && min_w>low_dis[i])
            {
                min_w=low_dis[i];
                point=i;
            }
        }
        s=point;
        u[s]=true;
        prim_w+=min_w;
        m++;
    }
    return prim_w;
}

int main(int i,int j)
{
    int test;
    cin>>test;
    while(test--)
    {
        memset(node,0,sizeof(node));
        num=0;
        cin>>x>>y;
        char temp[20];
        gets(temp);
        for(i=0;i<y;i++)
        {
            gets(map[i]);
            for(j=0;j<x;j++)
            {
                if(map[i][j]=='A'||map[i][j]=='S')
                    node[i][j]=++num;
            }
        }
        for(i=0;i<y;i++)
            for(j=0;j<x;j++)
                if(node[i][j])
                    bfs(i,j);
        cout<<prim()<<endl;
    }
    return 0;
}