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;
}