Problem 1296 最小生成树

来自NEUACM WIKI
跳转到: 导航, 搜索
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,tt,g[2501][250],f[60][60],f1[60][60],a[60][60],b[3600][5],c[10000][5],dir[100][10];
void dog(int x,int y,int z)
{
 int i,j,t1,t2,x1,y1;
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
   f1[i][j]=f[i][j]=0;
 t1=0;
 t2=1;
 c[1][0]=x;
 c[1][1]=y;
 f[x][y]=1;
 while(1)
 {
  t1++;
  if (t1>t2) break;
  x1=c[t1][0];
  y1=c[t1][1];
  for(i=0;i<=3;i++)
   if ((x1+dir[i][0]<=n)&&(x1+dir[i][0]>0)&&(y1+dir[i][1]<=m)&&(y1+dir[i][1]>0))
    if ((f[x1+dir[i][0]][y1+dir[i][1]]==0)&&(a[x1+dir[i][0]][y1+dir[i][1]]!=-1))
    {
     t2++;
     c[t2][0]=x1+dir[i][0];
     c[t2][1]=y1+dir[i][1];
     f[x1+dir[i][0]][y1+dir[i][1]]=1;
     f1[x1+dir[i][0]][y1+dir[i][1]]=f1[x1][y1]+1;
    }
 }
 for(i=1;i<=tt;i++)
  g[z][i]=f1[b[i][0]][b[i][1]];
}
 
int main()
{
 int i,j,k,max,max1,t,p[10000],pp[10000],ttt;
 char x;
 dir[0][0]=1;
 dir[0][1]=0;
 dir[1][0]=-1;
 dir[1][1]=0;
 dir[2][0]=0;
 dir[2][1]=1;
 dir[3][0]=0;
 dir[3][1]=-1;
 scanf("%d",&t);
 for(i=1;i<=t;i++)
 {
  scanf("%d%d",&m,&n);
  tt=0;
  while(1)
  {
   scanf("%c",&x);
   if (x==10) break;
  }
  for(j=1;j<=n;j++)
  {
   for(k=1;k<=m;k++)
   {
    scanf("%c",&x);
    if (x==' ') a[j][k]=0;
    if (x=='#') a[j][k]=-1;
    if ((x=='S')||(x=='A') )
    {
     tt++;
     a[j][k]=tt;
     b[tt][0]=j;
     b[tt][1]=k;
    }
   }
   scanf("%c",&x);
  }
  for(j=1;j<=tt;j++)
   dog(b[j][0],b[j][1],j);
  for(j=1;j<=tt;j++)
  {
   p[j]=0;
   pp[j]=100000000;
  }
  pp[1]=0;
  ttt=0;
  for(j=1;j<=tt;j++)
  {
   max=100000000;
   for(k=1;k<=tt;k++)
    if ((p[k]==0)&&(pp[k]<max)){max=pp[k];max1=k;}
   p[max1]=1;
   ttt+=max;
   for(k=1;k<=tt;k++)
    if ((p[k]==0)&&(pp[k]>g[max1][k])) pp[k]=g[max1][k];
  }
  printf("%d\n",ttt);
 }
 cin>>ttt;
 return 0;
}
 
 
 
/**************************************************************
	Problem: 1296
	User: ipqhjjybj
	Language: C++
	Result: 正确
	Time:39 ms
	Memory:4016 kb
****************************************************************/
个人工具
名字空间

变换
操作
导航
工具箱