解题思路

题目分析

本题是旅行商问题在特殊矩形网格（Gridland）场景下的应用。在Gridland中，城镇分布在矩形网格点上，道路向八个方向延伸（只要有相邻城镇），道路长度按欧几里得距离衡量，目标是计算能让销售员访问每个城镇恰好一次并回到起点的最短路径长度。

代码实现思路

1. 输入处理
   • 首先读取场景数量 num 。
   • 然后通过循环，对每个场景读取网格维度 m（行数）和 n（列数） 。
2. 路径长度计算
   • 核心在于根据 m 和 n 的奇偶性来确定最短路径长度：
     • 当 m 和 n 都为奇数时：
       • 可以想象在这种情况下，走遍所有点并回到起点，会有一段对角线的路径。因为矩形网格的点数是 m * n 个，正常横向纵向走会有 m * n - 1 段长度为 1 的路径，再加上一段对角线（其长度根据勾股定理，在单位方格中为 sqrt(2.0) ），所以总路径长度为 m * n - 1 + sqrt(2.0) 。
     • 其他情况（即 m 和 n 不同时为奇数）：
       • 此时可以通过合理规划路径，只通过横向和纵向的边遍历所有城镇并回到起点，不存在额外的对角线边。由于横向和纵向边长为 1 ，总共需要经过 m * n 段这样的边，所以路径长度就是 m * n 。
3. 输出处理
   • 按照题目要求的格式输出每个场景的结果，包括场景编号，最短路径长度（保留两位小数），并且每个场景输出后换行。

时间复杂度分析

整个程序主要操作是输入数据、简单的条件判断和计算，时间复杂度主要取决于输入场景的数量。对于每个场景，计算和输出操作都是常数时间的操作。设场景数量为 T ，那么总体时间复杂度为 $O(T)$ 。

空间复杂度分析

程序中除了输入数据占用的空间外，只使用了几个简单的变量（如 num、m、n、i、res 等）来存储中间结果，这些变量占用的空间与输入规模无关，所以空间复杂度为 $O(1)$ 。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main()
{
    int num;
    cin>>num; // 读取场景数量
    int m,n,i;
    double res;
    for(i=1;i<=num;i++) // 遍历每个场景
    {
        cin>>m>>n; // 读取当前场景网格的行数m和列数n
        if(m%2==1 && n%2==1) // 判断m和n是否都为奇数
            res=m*n-1+sqrt(2.0); // 若都为奇数，按对应公式计算路径长度
        else
            res=m*n; // 否则按另一种情况计算路径长度
        printf("Scenario #%d:\n",i); // 输出场景编号
        printf("%0.2lf\n",res); // 输出最短路径长度，保留两位小数
        printf("\n"); // 换行，符合题目每个场景输出后空行的要求
    }
    return 0;
}