|
|
|
|
|
网格王国
|
||||
背景 多年来，计算机科学家们对于许多计算问题已经找到了有效的解法，而且一些解法是可用的，例如：排序算法、图的最短路问题等，都有多项式的解法。它们都是很容易解决的问题了。同时还有许多运算级别为指数级的问题，例如旅行商问题：给定N个城镇和城镇之间路，计算出一条允许一个商人访问每个城镇一次且仅访问一次，并回到起点的最短路径。 问题 网格王国的总统请你编写一个程序计算出游行商遍历所有该王国中的所有城市的最短路径的长度。在这个网络王国中，整个国家是一个矩形网格，网络的每一个格点上是一个城市，王国中连接相邻两个城市的道路可以有下面八种方向中的一种：北、西北、西、西南、南、东南、东、东北。南北、或东西方向的任意相邻两个城市的距离为1个单位。例如下图表示一个2＊3的网格王国（一个2行3列的矩形网格），它的最短遍历长度为6个单位。  一个在2 × 3的网格王国中的遍历路径 输入： 输入的第一行是一个整数，表示测试数据的个数。接下来，每行表示一个测试数据，有两个整数m和n，表示一个网格的行数与列数。这里1 < m < 50 且1 < n < 50。 输出： 对于每个数据输出的第一行为："Scenario #i:"，这里i是测试数据的编号（编号从1开始），第二行是最短的遍历路径的长度，结果保留两位小数。每个测试数据的输出以一个空行结束。 Sample Input 2 2 2 2 3 Sample Output Scenario #1: 4.00 Scenario #2: |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |