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