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

79愛的鼓勵 1訂閱站台

作法 : DFS 搜尋

在此提供兩種作法 : (1)由大往小走 (2)由小往大走

大家一定認為這兩者沒有差別,但是所能提供的判斷就是不同...(應該吧)

最快的為第2程式碼.

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[102][102]={0};
int max;
int t,n,m;
long long int input()  
{  
  char cha;  
  unsigned long long 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;  
}
void DFS (int x,int y,int s)
{
   if(s>max) max=s;
   if(map[x+1][y]<map[x][y]&&x+1<=n&&map[x+1][y]+s>=max)
       DFS(x+1,y,s+1);
   if(map[x-1][y]<map[x][y]&&x-1>0&&map[x-1][y]+s>=max)
       DFS(x-1,y,s+1);
   if(map[x][y+1]<map[x][y]&&y+1<=m&&map[x][y+1]+s>=max)
       DFS(x,y+1,s+1);
   if(map[x][y-1]<map[x][y]&&y-1>0&&map[x][y-1]+s>=max)
       DFS(x,y-1,s+1);
}
main()
{
  char name[100];
  scanf("%d",&t);
  while(t--)
     {
        scanf("%s %d %d",name,&n,&m);
        int a,b,c;
        max=0;
        for(a=1;a<=n;a++)
           for(b=1;b<=m;b++)
              map[a][b]=input();
        for(a=1;a<=n;a++)
           for(b=1;b<=m;b++)
              if(map[a][b]>max)
                    DFS(a,b,1);
         printf("%s: %d\n",name,max);         
     }
 return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[102][102]={0},path[102][102]={0};
int max;
int t,n,m,temp;
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;     
}  
void DFS (int x,int y,int s)
{
   if(s>temp) temp=s;
   if(map[x+1][y]>map[x][y]&&x+1<=n&&path[x+1][y]<=s)
       {
        path[x+1][y]=s+1;
        DFS(x+1,y,s+1);
       }
   if(map[x-1][y]>map[x][y]&&x-1>0&&path[x-1][y]<=s)
       {
        path[x-1][y]=s+1;
        DFS(x-1,y,s+1);
       }
   if(map[x][y+1]>map[x][y]&&y+1<=m&&path[x][y+1]<=s)
       {
        path[x][y+1]=s+1;
        DFS(x,y+1,s+1);
       }
   if(map[x][y-1]>map[x][y]&&y-1>0&&path[x][y-1]<=s)
       {
        path[x][y-1]=s+1;
        DFS(x,y-1,s+1);
       }
}
main()
{
  char name[100];

  scanf("%d",&t);
  while(t--)
     {
        scanf("%s %d %d",name,&n,&m);
        int a,b,c;
        max=0;
        for(a=1;a<=n;a++)
           for(b=1;b<=m;b++)
              {
              map[a][b]=input();
              path[a][b]=0;
              }
        for(a=1;a<=n;a++)
           for(b=1;b<=m;b++)
              if(path[a][b]==0)
                  {
                    temp=0;
                    DFS(a,b,1);
                    if(temp>max) max=temp;
                  } 
         printf("%s: %d\n",name,max);         
     }
 return 0;
}