黑马程序员技术交流社区

标题: ACM国际大学生程序设计竞赛 : 基础篇01 [打印本页]

---

作者: _J2EE_LiXiZhen    时间: 2017-11-5 22:35
标题: ACM国际大学生程序设计竞赛 : 基础篇01


题目大意：给出一个nxm的矩阵，现在从某点开始遍历所有点并回到起始点，问最少的遍历路程是多少？(从某点出发有8个方向，行上相邻的点之间的距离是1。)

  数理分析：其实这道题目的描述非常有误导性，多次强调所谓“旅行销售员问题”，也就是当现在还没有得到很好解决的著名的TSP问题，这就很容易将人带向很混乱的思维。但是这道题目基于比较特殊的矩阵图，我们应该能够更加简单的方法。

  我们首先应该考虑到的一个贪心策略，行走距离为1的利益最大化就是访问到了一个节点(当然不算起始节点)，那么如果有这样一种方案使得我们，遍历距离+1，都会导致多访问了1个节点，那么这最终一定会导致最小的路程，即节点个数mn。

  那么下面我们所关注的问题便是，是否存在这样一个策略呢？如果m列是偶数，那么连接相邻节点形成小正方格，就会形成奇数列个小方格，这使得我们能够有一个走“S”型的锯齿状的遍历策略，能够使我们完成贪心策略。

  即我们能够得到结论，如果m、n当中有一个是偶数，最小距离都是mn。

  那么如果m、n都是奇数呢？依然从m列入手，我们基于(m-1)xn这样一个矩阵，那么我们可以采取和上面类似的思路进行贪心化的遍历，由此我们其实能够看到，对于这种情况，是没有一种路程为mn的便利方案的，但对于剩下的两列，一开始我们令遍历路线走一个长为1.41的“斜边”，然后由原来的纵向S型变成横向S型，即路程为mn + 0.41，这是除去路程为mn的最优方案。

  上文给出的文字描述可能过于抽象，读者可以自行画图感受一下。

  综合起来我们能够得到这道问题线性算法：

  m、n存在一个偶数，结果是mn。

  否自，结果是mn + 0.41.

简单的参考代码如下：

[C] 纯文本查看 复制代码

#include<cstdio>

using namespace std;



int main()

{

     int t;

     scanf("%d",&t);

     int tt  =1;

     while(t--)

     {

          int n , m;

          scanf("%d %d",&n,&m);

          if(n % 2 == 0 || m%2 == 0)

                printf("Scenario #%d:\n%d.00\n",tt++,m*n);

          else

                printf("Scenario #%d:\n%d.41\n",tt++,m*n);



          printf("\n");

     }

}

---

作者: Oliverwqcwrw    时间: 2017-11-5 22:56
66666666666666666666666

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2