链接:poj 3026

题意：y行x列的迷宫中，#代表阻隔墙（不可走），空格代表空位（可走），S代表搜索起点（可走）

A代表外星人站（可走），现在要从S出发，每次可上下左右移动一格到可走的地方，求到达所有的A

的路线总距离最小值

分析：可以先用bfs从上下左右四个方向将所有的A,S两两之间的最短距离，题目的目的是将S与所有的A连通，

使得总距离最小，所以任选一点开始按最小生成树的算法做就行，并非非要从S点开始

注：题目输入x,y后可能有很多空格，可以用gets将多余的空格取走，开数组是尽量开大点，之前虽然开的比题目数 据稍大，但一直错，改大就AC了、、、题目数据不忍直视

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int dx[]={1,0,-1,0}; const int dy[]={0,1,0,-1}; int m,n,x,y,f[1050],num[1050][1050]; //之前都是105 struct point { int i,j; }a[1050]; struct stu { int a,b,c; }t[100500]; //之前开的10050 char s[100][100]; int cmp(struct stu x1,struct stu x2) { return x1.c
      
        q; struct point d; memset(dis,0,sizeof(dis)); memset(v,0,sizeof(v)); q.push(a[star]); v[a[star].i][a[star].j]=1; while(!q.empty()){ d=q.front(); q.pop(); i=d.i; j=d.j; if(s[i][j]=='A'||s[i][j]=='S'){ t[m].a=star; t[m].b=num[i][j]; t[m++].c=dis[i][j]; } for(k=0;k<4;k++) { d.i=i+dx[k]; d.j=j+dy[k]; if(d.i>=0&&d.i
       
        =0&&d.j