71
poj 1450 Gridland
我在之前的博文裏麵提到過：比賽的時候最怕做字符串處理或者是那種不斷WA，卻是因為一個字母是小寫的題目。。。
那像1450這種題就是比賽中最希望碰到的題目。。。這種題就是讀懂題目最重要，讀懂了題目找到了規律，基本上在10分鍾以內可以A掉。。。
題目大意：給出一個n×m的矩陣，每個點可以朝上下左右，還有4個斜著的方向走
問從某點出發，走遍所有的點的最短距離，每個點隻能經過一次
很簡單的一道題目，分奇數偶數進行判定，兩個數都奇數就再加0.41。
在圖上尋找規律後，容易看出，當M或N是偶數，或者都是偶數，最短距離為M*N。而當M和N都是奇數，則必有一條或以上的卸徑，而最短距離是M*N-1+sqrt(2)。一定要畫圖才能明白
看了網上的結題報告，基本也都是這種方法。。。
AC的代碼：
#include<iostream>
int main()
{
int a,m,n,i;
double s;
scanf("%d",&a);
for(i=1;i<=a;i++)
{
scanf("%d%d",&m,&n);
s=m*n;
if(m*n%2==1)
{
s+=0.41; //根號 2 約等於1.414，-1+1.414=0.414
printf("Scenario #%d:\n%.2lf\n\n",i,s);
}
else
printf("Scenario #%d:\n%.2lf\n\n",i,s);
}
return 0;
}
最後更新：2017-04-03 14:54:00