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

79愛的鼓勵 1訂閱站台

作法 : DFS

目前沒有任何人過,所以我也不曉得此作法是否正確.

不過大致上就是利用遞迴去做探訪

不過作探訪的同時,把走過的路做上標記,並且不要走回去,而在退回的部份

要把標記刪除,才能用別的路徑通過這一點

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

#include<stdio.h>
#include<stdlib.h>
int map[30][30]={0},max=0,used[30][30]={0};
void DFS (int x,int y,int sum)
{
   if(map[x+1][y]!=-10&&used[x+1][y]==0)
      {
        if(map[x+1][y]==-11)
             {if(sum>max) max=sum;}
        else
          {
           used[x+1][y]=1;
           DFS(x+1,y,sum+map[x+1][y]);
           used[x+1][y]=0;
          }
      }
   if(map[x-1][y]!=-10&&used[x-1][y]==0)
      {
        if(map[x-1][y]==-11)
             {if(sum>max) max=sum;}
        else
          {
           used[x-1][y]=1;
           DFS(x-1,y,sum+map[x-1][y]);
           used[x-1][y]=0;
          }
      }
   if(map[x][y+1]!=-10&&used[x][y+1]==0)
      {
        if(map[x][y+1]==-11)
             {if(sum>max) max=sum;}
        else
          {
           used[x][y+1]=1;
           DFS(x,y+1,sum+map[x][y+1]);
           used[x][y+1]=0;
          }
      }
   if(map[x][y-1]!=-10&&used[x][y-1]==0)
      {
        if(map[x][y-1]==-11)
             {if(sum>max) max=sum;}
        else
          {
           used[x][y-1]=1;
           DFS(x,y-1,sum+map[x][y-1]);
           used[x][y-1]=0;
          }
      }
}
main()
{
  int a,b,c,n,m,h;
  char s[30];
  while(scanf("%d %d %d",&n,&m,&h)==3)
      {
       int startx,starty;
         for(a=0;a<n;a++)
            {
              scanf("%s",s);
              for(b=0;b<m;b++)
                 if(s[b]=='*')  map[a][b]=-10;
                 else if(s[b]=='S')  {startx=a;starty=b;}
                 else if(s[b]=='E')  map[a][b]=-11;
                 else if(s[b]<='D'&&s[b]>='A')  map[a][b]=(s[b]-'A'+1)*-1;
                 else map[a][b]=1;
            }
         used[startx][starty]=1;
         max=0;
         DFS (startx,starty,0);
         if(h==max)
            printf("OK!\n",max);
         else if(h<max)
            printf("=] %d\n",max);  
         else
            printf("=[ %d\n",max);
         used[startx][starty]=0;
      }
 return 0;
}