题意：y行x列的迷宫中，#代表阻隔墙（不可走）。空格代表空位（可走）。S代表搜索起点（可走）,A代表目的地（可走），如今要从S出发，每次可上下左右移动一格到可走的地方。求到达全部的A的路线总距离最小值
分析：能够先用bfs从上下左右四个方向将全部的A,S两两之间的最短距离，题目的目的是将S与全部的A连通，使得总距离最小，所以任选一点開始按最小生成树的算法做即可，并不是非要从S点開始
注：题目输入x,y后可能有非常多空格，能够用gets将多余的空格取走，开数组是尽量开大点。之前尽管开的比题目数据稍大，但一直错，改大就AC了、、、题目数据不忍直视
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
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<x2.c;
}
void bfs(int star)
{
int i,j,k,dis[100][100],v[100][100];
queue<struct point> 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<y&&d.j>=0&&d.j<x&&!v[d.i][d.j]&&s[d.i][d.j]!='#')
{
q.push(d);
v[d.i][d.j]=1;
dis[d.i][d.j]=dis[i][j]+1;
}
}
}
}
int find(int r)
{
if(r!=f[r])
f[r]=find(f[r]);
return f[r];
}
int krus()
{
int i,k=0,sum=0,l,r;
for(i=1;i<m;i++){
l=find(t[i].a);
r=find(t[i].b);
if(l!=r){
sum+=t[i].c;
k++;
if(k==n-1)
break;
f[l]=r;
}
}
return sum;
}
int main()
{
int N,i,j,sum;
char c[55];
scanf("%d",&N);
while(N--){
scanf("%d%d",&x,&y);
gets(c); //将多余空格取走
n=1;
for(i=0;i<y;i++){
gets(s[i]);
for(j=0;j<x;j++)
if(s[i][j]=='A'||s[i][j]=='S'){
a[n].i=i; //存A或S的坐标
a[n].j=j;
num[i][j]=n++; //存点的序号
}
}
n--;
m=1;
for(i=1;i<=n;i++){
f[i]=i; //初始化父节点
bfs(i); //求以i为一个顶点的全部边的权值
}
sort(t+1,t+m,cmp);
sum=krus();
printf("%d\n",sum);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。