HDU1046：Gridland

佚名 6年前 (2019-04-09) 随笔 1015人围观抢沙发百度已收录

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

然而是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);
    }