NYOJ818ZOJ--1037---Gridland

Gridlandの大統領はあなたを雇ってプログラムを作成し、この国のすべての都市の旅行販売員の問題の最短距離を計算します.Gridlandでは、各都市は矩形メッシュの1つの点に位置します.各都市への道は東、西、南、北、東南、東北、南西、北西方向のみで、各方向に隣接する都市は1つしかありません.東西、南北方向の長さは1.長さの単位はユークリッド距離です.図に示すように2 X 3のGrilandで、最短の周遊コース長は6です.入力:最初の行は、1行に2つの整数mとn(1  Sample input 2 2 2 2 3 Sample output Scenario #1: 4.00  Scenario #2: 6.00
Source: Northwestern Europe 2001
分析:
最初は問題を解く者を最小の経路、図論の方向に考え、また問題の表現もよく分からなかった.
問題は、gridlandという国があり、nつの都市と都市間の距離を与えることです.問題は、販売員が都市ごとに1回しか訪問しないように最短の経路を探して出発点に戻ることです.gridlandの大統領は、この国のすべての都市の旅行販売員問題の最短長さを計算するプログラムを作成させます.gridlandでは、各都市が矩形ネットワークの1つの点に位置しています.各都市に通じる道路は東、西、南、北、東北、東南、南西、西北、方向だけで、各方向に隣接する都市が1つしかなく、東西南北方向の長さは1で、長さの単位はユークリッド距離で、図のように、最短周遊ルートの長さは6です.
アルゴリズム分析:簡単な図面を描くことで、入力した長さと幅の積が偶数であれば、最も短い距離は長さと幅の積であり、すなわち最短距離はm*nであり、入力した長さと幅の積が奇数であれば、直辺、すなわち最短距離はm*n+sqrt(2)-1の代わりに斜辺を歩く必要があり、結果は2桁の小数を残すことに注意する.
参照コード:

#include<stdio.h>
int main()
{
	int t, n, m, i = 0;
	scanf("%d",&t);
	while(t--)
	{
	    scanf("%d%d",&m,&n);
		printf("# %d:
",++i);
		if(m*n%2!=0)
			printf("%d.41
",m*n);
	else
			printf("%d.00
",m*n);
	}
	return 0;
}