2008 海峽兩岸青少年程式設計競賽 雷曼兔
作法:不太像是最短路徑,一直做更新的動作
由於是樹枝狀的圖,所以只要有順序的更新,便不會產生邏輯的錯誤
有環的或著是...就不行 以上
/**********************************************************/
#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;
}
上一篇:昇旗典禮