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

79愛的鼓勵 1訂閱站台

作法:不太像是最短路徑,一直做更新的動作

由於是樹枝狀的圖,所以只要有順序的更新,便不會產生邏輯的錯誤

有環的或著是...就不行 以上

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int num[2501][2]={0};
main()
{
 int n;
 while(scanf("%d",&n)==1)
   {
     int a,b,c,m;
     for(a=1;a<=n;a++)
      for(b=1;b<=n;b++)
       {
        scanf("%d",&m);
        num[m][0]=a;
        num[m][1]=b;
       }
     
     int way[2501]={0};
      for(b=1;b<=n*n;b++)
       for(c=1;c<b;c++)
         {
           int ll=(abs(num[b][0]-num[c][0])+abs(num[b][1]-num[c][1]))*(abs(num[b][0]-num[c][0])+abs(num[b][1]-num[c][1]));
           int temp=way[c]+ll;
           way[b]=(temp>way[b])?temp:way[b];
         }
       printf("%d\n",way[n*n]); 
   }
 return 0;
}