| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
那位大牛帮我看看我哪儿错了!不胜感激!我都错了快二十次了!可是就是找不出来哪儿错了!修改了一次又一次!晕惨了!
#include<iostream>
using namespace std;
#define maxx 1000000000
int t,n,m,node[201][201],dist[201],visit[201],num[201][2],mark[51][51];
char str[81][81];
int step[4][2]={1,0,-1,0,0,1,0,-1};
void bfs(int a,int b,int sk,int ne)
{
int q[3001],qx[3001],qy[3001],vist[51][51],xx,yy,i,j,t,e,kk=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
vist[i][j]=0;
vist[b][a]=1;
qx[0]=a,qy[0]=b,q[0]=0;
str[b][a]='#';
t=0,e=1;
while(t<e)
{
for(i=0;i<4;i++)
{
xx=qx[t]+step[i][0];
yy=qy[t]+step[i][1];
if(xx>=0&&xx<m&&yy>=0&&yy<n&&vist[yy][xx]==0&&str[yy][xx]!='#')
{
vist[yy][xx]=1;
qx[e]=xx,qy[e]=yy;
q[e]=q[t]+1;
if(str[yy][xx]=='A'||str[yy][xx]=='S')
node[mark[yy][xx]][sk]=node[sk][mark[yy][xx]]=q[e],kk++;
e++;
}
}
if(kk==ne)
break;
t++;
}
}
void prime(int len)
{
int i,j,k,mine,sum=0;
for(i=1;i<len;i++)
node[i][i]=0;
for(i=1;i<len;i++)
dist[i]=node[1][i],visit[i]=0;
visit[1]=1;
for(i=2;i<len;i++)
{
mine=maxx;
for(j=1;j<len;j++)
{
if(visit[j]==0&&dist[j]<mine)
{
mine=dist[j];
k=j;
}
}
sum+=mine;
visit[k]=1;
for(j=1;j<len;j++)
if(visit[j]==0&&node[k][j]<dist[j])
dist[j]=node[k][j];
}
printf("%d\n",sum);
}
int main()
{
scanf("%d",&t);
int i,j,len;
while(t--)
{
len=1;
scanf("%d%d",&m,&n);
getchar();
for(i=0;i<n;i++)
gets(str[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(str[i][j]=='A'||str[i][j]=='S')
{
mark[i][j]=len;
num[len][0]=i,num[len][1]=j;
len++;
}
for(i=1;i<len;i++)
for(j=i;j<len;j++)
node[i][j]=node[j][i]=maxx;
for(i=1;i<len;i++)
bfs(num[i][1],num[i][0],i,len-i-1);
prime(len);
}
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator