http://www.shnenglu.com/jh818012/articles/165674.html這個是我sb隊友寫的題解，一看就發(fā)現(xiàn)了錯誤，哈哈哈，不過AC了?。。?！
bfs+prim，我不懂floodfill，不過bfs還是懂的。今晚終于寫了個bfs了，AC真是爽啊。哈哈哈哈哈，
悲催的數(shù)據(jù)的輸入，要注意注意呀，以后涉及字符串輸入的，都要小心哈！用gets()比較好哦啊
#include<stdio.h>
#include<string.h>
#include<math.h>
int x,y,tot;
int map[2505][2505],a[10005],b[10005],p[2505],que[1000005];
int dis[2505],vis[2505];
int bfs(int s)
{
int head,tail,i,x1,y1,now;
memset(b,0,sizeof(b));
que[1]=p[s];
b[p[s]]=1;
head=0;
tail=1;
while (head<tail)
{
head++;
now=que[head];
x1=(now-1)/y+1;
y1=(now-1)%y+1;
if (x1>1&&!b[now-y]&&a[now-y])
{
tail++;
que[tail]=now-y;
b[now-y]=b[now]+1;
}
if (x1<x&&!b[now+y]&&a[now+y])
{
tail++;
que[tail]=now+y;
b[now+y]=b[now]+1;
}
if (y1>1&&!b[now-1]&&a[now-1])
{
tail++;
que[tail]=now-1;
b[now-1]=b[now]+1;
}
if (y1<y&&!b[now+1]&&a[now+1])
{
tail++;
que[tail]=now+1;
b[now+1]=b[now]+1;
}
}
for (i=1; i<=tot ; i++ )
map[s][i]=b[p[i]]-1;
}
int prim()
{
int i,j,sum,min,minj;
for (i=1; i<=tot ; i++ )
{
dis[i]=100000000;
vis[i]=1;
}
sum=0;
dis[1]=0;
for (i=1; i<=tot ; i++ )
{
min=100000000;
for (j=1; j<=tot ; j++ )
if (dis[j]<min&&vis[j])
{
min=dis[j];
minj=j;
}
sum+=min;
vis[minj]=0;
for (j=1; j<=tot ; j++ )
if (vis[j]&&map[minj][j]<dis[j])
dis[j]=map[minj][j];
}
return sum;
}
int init()
{
int i,j;
char ch[55];
scanf("%d%d",&y,&x);
tot=0;
gets(ch);
for (i=1; i<=x ; i++ )
{
gets(ch);
for (j=1; j<=y ; j++ )
{
if (ch[j-1]=='#')
a[i*y-y+j]=0;
else if (ch[j-1]==' ')
a[i*y-y+j]=1;
else
{
tot++;
p[tot]=i*y-y+j;
a[i*y-y+j]=1;
}
}
}
}
int work()
{
int i,ans;
for (i=1; i<=tot ; i++ )
bfs(i);
ans=prim();
printf("%d\n",ans);
}
int main()
{
int n;
scanf("%d",&n);
while (n>0)
{
n--;
init();
work();
}
return 0;
}
要開始注意代碼風格了，我的代碼太難看啦?。?！