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

79愛的鼓勵 1訂閱站台

作法 : DP  逐步找最佳解.

還有更短的寫法,沒人提供...

EX.

   0 1  2 3 X

0  0 7  8 9
1  1 5  1 1
2  2 4 10 0

Y

先在要從 (0,0)→ (3,2) !

首先 從左上開始 (右下也可以)

然後座標 (0,0)附近有 (0,1) (1,0) 兩個座標

那麼我必定知道 (0,0) 走到 (0,1) (1,0) 的最短路徑  (比上比左的總和)

因此改變圖變成  (根本沒變)

   0 1  2 3 X

0  0 7  8 9
1  1 5  1 1
2  2 4 10 0

Y

之後因為知道 到(0,1) (1,0)的最短路徑 那麼我必定知道

(0,2) (1,1) (2,0) 的最短路徑

首先是 (0,2) 的點 只有 1+2 =3
      (1,1) 的點 發現 1+5 < 5+7  此點存放 1+5
      (2,0) 的點 只有 7+8=15

因此改變圖變成 

   0 1  2 3 X

0  0 7 15 9
1  1 6  1 1
2  3 4 10 0

Y

之後因為知道 到(0,2) (1,1) (2,0)的最短路徑 那麼我必定知道

(1,2) (2,1) (3,0) 的最短路徑

首先是 (1,2) 的點 只有 3+4 < 6+4  此點存放 3+4
      (2,1) 的點 發現 1+6 < 15+1  此點存放 1+6
      (3,0) 的點 只有 15+9=24

因此改變圖變成 

   0 1  2  3 X

0  0 7 15 24
1  1 6  7  1
2  3 7 10  0

Y

之後因為知道 到(1,2) (2,1) (3,0)的最短路徑 那麼我必定知道

(2,2) (3,1) 的最短路徑

首先是 (2,2) 的點 只有 7+1 < 1+24  此點存放 1+7
      (3,1) 的點 發現 10+7 = 10+7  此點存放 10+7

因此改變圖變成 

   0 1  2  3 X

0  0 7 15 24
1  1 6  7  8
2  3 7 17  0

Y

最後右下角比較上跟左的點

輸出 8 !

講了這麼多寫起來還是有點困難.所以應該是要用queue(佇列...)

一直把鄰近的點丟進去...然後逐一比對.由於先進先出

只要不要重複把點丟進去queue裡順序就不會錯....

 

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

#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;  
}
main()  
{  
 int n,m,time=0;
 while(scanf("%d %d",&n,&m)==2)
     {
        int a,b;
        int data[101][101]={0},minpath[101][101]={0},appear[101][101]={0};
        for(a=0;a<n;a++)
           for(b=0;b<m;b++)
              {
                data[a][b]=input();
                minpath[a][b]=100000000;
              }
        minpath[0][0]=0;
        int queue[10000][2]={0},top=1;
        queue[0][0]=0;queue[0][1]=1;
        queue[1][0]=1;queue[1][1]=0;
        appear[1][0]=1;
        appear[0][1]=1;
        appear[0][0]=1;
        for(a=0;a<=top;a++)
           {
              int x=queue[a][0],y=queue[a][1];
              if(x-1>=0)
              minpath[x][y]=minpath[x-1][y]+data[x][y];
              if(y-1>=0)
              minpath[x][y]=(minpath[x][y-1]+data[x][y]<minpath[x][y])?(minpath[x][y-1]+data[x][y]):minpath[x][y];
              if(x+1<n&&appear[x+1][y]==0)
                 {top++;queue[top][0]=x+1;queue[top][1]=y;appear[x+1][y]=1;}
              if(y+1<m&&appear[x][y+1]==0)
                 {top++;queue[top][0]=x;queue[top][1]=y+1;appear[x][y+1]=1;}
           }
         printf("Case #%d :\n",++time);
         printf("%d\n",minpath[n-1][m-1]);
     }
 return 0;   
}