HDU1046：Gridland

题目大意：给出一个n*m的矩阵，现在从某点开始遍历所有点并回到起始点，问最少的遍历路程是多少（边长为1,可以走对角线）？

n<50,m<50？那岂不是应该\(O(n^4)\)左右的算法？

然而是O(1)

如果n，m中有至少一个是偶数，那么ans=n*m

如果都是奇数，至少要走一个对角线，可以构造出仅走一个对角线的路线

    int n;
    cin>>n;
    for(int i = 1; i <= n; ++i){
        int a, b;
        double ans;
        cin>>a>>b;
        if(a % 2 == 0 || b % 2 == 0){
            ans = a * b;
        }else{
            ans = a * b - 1 + sqrt(2);
        }
        printf("Scenario #%d:\n", i);
        printf("%.2f\n\n", ans);
    }

HDU1046：Gridland

原文：https://www.cnblogs.com/Doingdong/p/10679712.html