这个题是NP旅行商问题的简化版，求的是一个矩阵上的最短的路径。

NP旅行商问题是Given a set of N towns and roads between these towns, the problem is to compute the shortest path allowing a salesman to visit each of the towns once and only once and return to the starting point.只不过这道题是将这N towns 放在了一个矩阵上，这样可以找到规律,如下：

设矩阵为M*N,如果M和N都是奇数，那么最短的路径中有且仅有一条斜边，即√2的单位长度，答案是M*N-1+√2

其他情况 答案是M*N

下面是代码，注意sqrt()的参数是double型，即sqrt(2.0);

#include 
      
       #include 
       
        #include 
        
         using namespace std;int main(){    int num;    cin>>num;    int m,n,i;    double res;    for(i=1;i<=num;i++)    {        cin>>m>>n;        if(m%2==1 && n%2==1)            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;}
        
       
      

这个题在tju oj1015也出现过。