摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

遞迴的DFS

/***********************************************************/

#include<stdio.h>                 
#include<stdlib.h>     
int map[102][102];
void map2(int b,int a,int ans)
{
  if(map[b-1][a]>0) { map[b-1][a]=ans;map2(b-1,a,ans); }
  if(map[b][a-1]>0) { map[b][a-1]=ans; map2(b,a-1,ans); }
  if(map[b][a+1]>0) { map[b][a+1]=ans; map2(b,a+1,ans); }
  if(map[b+1][a]>0) { map[b+1][a]=ans; map2(b+1,a,ans); }
}
main()     
{     
 int a,b,c,n,m,time=0;
 while(scanf("%d %d",&n,&m)==2)
  {
   int grass[102][102],ans2[10000]={0},max=0;
   for(a=0;a<102;a++)
    for(b=0;b<102;b++)
     map[a][b]=0;
   int ans=0;
   for(b=1;b<=n;b++)
     for(a=1;a<=m;a++)
      {
       scanf("%d",&map[b][a]);
       grass[b][a]=map[b][a];
      }
   
    for(b=1;b<=n;b++)
      for(a=1;a<=m;a++)
        if(map[b][a]>0)
         {
          ans--;
          map[b][a]=ans;
          map2(b,a,ans);
         }
    for(b=1;b<=n;b++)
      for(a=1;a<=m;a++)
       ans2[abs(map[b][a])]+=grass[b][a];
    ans=abs(ans);
    for(a=1;a<=ans;a++)
     if(ans2[a]>max) max=ans2[a]; 
    printf("%d\n%d\n",abs(ans),max);
  }
 return 0;     
}

/**********************************************************/

優化輸入...優一下8Xms...

#include<stdio.h>                    
#include<stdlib.h>        
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
int map[102][102];  
void map2(int b,int a,int ans)  
{  
  if(map[b-1][a]>0) { map[b-1][a]=ans;map2(b-1,a,ans); }  
  if(map[b][a-1]>0) { map[b][a-1]=ans; map2(b,a-1,ans); }   
  if(map[b][a+1]>0) { map[b][a+1]=ans; map2(b,a+1,ans); }   
  if(map[b+1][a]>0) { map[b+1][a]=ans; map2(b+1,a,ans); }   
}   
main()        
{        
 int a,b,c,n,m,time=0;  
 while(scanf("%d %d",&n,&m)==2)  
  {  
   int grass[102][102],ans2[10000]={0},max=0;  
   for(a=0;a<102;a++)  
    for(b=0;b<102;b++)  
     map[a][b]=0;  
   int ans=0;  
   for(b=1;b<=n;b++)   
     for(a=1;a<=m;a++)  
      {  
       map[b][a]=input(); 
       grass[b][a]=map[b][a];  
      }  
      
    for(b=1;b<=n;b++)  
      for(a=1;a<=m;a++)  
        if(map[b][a]>0)  
         {   
          ans--;  
          map[b][a]=ans;  
          map2(b,a,ans);   
         }  
    for(b=1;b<=n;b++)  
      for(a=1;a<=m;a++)  
       ans2[abs(map[b][a])]+=grass[b][a];  
    ans=abs(ans);  
    for(a=1;a<=ans;a++)  
     if(ans2[a]>max) max=ans2[a];    
    printf("%d\n%d\n",abs(ans),max);  
  }   
 return 0;        
}