题意：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];       //之前都是105struct point{    int i,j;}a[1050];struct stu{    int a,b,c;}t[100500];            //之前开的10050char 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
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。