菜鸟题解 ZOJ-1037 Gridland（未完待续）

原题直达

https://vjudge.net/contest/582185#problem/L

题干

原题面
参考翻译

For years, computer scientists have been trying to find efficient solutions to different computing problems. For some of them efficient algorithms are already available, these are the “easy” problems like sorting, evaluating a polynomial or finding the shortest path in a graph. For the “hard” ones only exponential-time algorithms are known. The traveling-salesman problem belongs to this latter group. 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.

The president of Gridland has hired you to design a program that calculates the length of the shortest traveling-salesman tour for the towns in the country. In Gridland, there is one town at each of the points of a rectangular grid. Roads run from every town in the directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast, provided that there is a neighbouring town in that direction. The distance between neighbouring towns in directions North–South or East–West is 1 unit. The length of the roads is measured by the Euclidean distance. For example, Figure 7 shows 2 × 3-Gridland, i.e., a rectangular grid of dimensions 2 by 3. In 2 × 3-Gridland, the shortest tour has length 6.

Input

The first line contains the number of scenarios.

For each scenario, the grid dimensions m and n will be given as two integer numbers in a single line, separated by a single blank, satisfying 1 < m < 50 and 1 < n < 50.

Output

The output for each scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. In the next line, print the length of the shortest traveling-salesman tour rounded to two decimal digits. The output for every scenario ends with a blank line.

多年来，计算机科学家一直在努力为不同的计算问题寻找有效的解决方案。对于其中一些高效的算法已经可用，这些是“简单”的问题，如排序，评估多项式或在图中找到最短路径。对于“硬”算法，我们只知道指数时间算法。旅行推销员问题属于后一类。给定一组N个城镇和这些城镇之间的道路，问题是计算允许销售人员访问每个城镇一次且仅一次并返回起点的最短路径。

Gridland公司的总裁雇你设计一个程序，计算全国各城镇旅行推销员的最短行程。在Gridland中，矩形网格的每个点上都有一个城镇。道路从每个城镇向北、西北、西、西南、南、东南、东和东北方向延伸，只要在该方向上有邻近的城镇。南北或东西方向相邻城镇之间的距离为1个单位。道路的长度是用欧氏距离来测量的。例如，图7显示了2 × 3- gridland，即尺寸为2 × 3的矩形网格。在2 × 3-Gridland中，最短的行程长度为6。

Input

第一行包含场景的数量。

对于每种情况，网格维度m和n将在单行中以两个整数给出，由单个空白分隔，满足1 < m < 50和1 <n < 50.

Output

每个场景的输出都以一行开头，其中包含“场景#i:”，其中i是从1开始的场景的编号。在下一行中，打印最短旅行推销员旅程的长度，四舍五入到两位小数。每个场景的输出都以空行结束。

测试案例

Input

1
2
3

2
2 2
2 3

Output

Scenario #1:
4.00

Scenario #2:
6.00

题意与思路

题意为给出一个最大不超过 4x4 的正方形表格，表格中有两种值：. 和 X 分别代表 空地 和 墙，你需要在空地摆放尽可能多的碉堡，满足：

墙的位置不能摆放碉堡
除非被墙遮挡，否则同一行、同一列中只能摆放一个碉堡

求最多能摆放多少碉堡。

核心思想：采用深度优先搜索的思想，遍历表格——

到达右下角，更新最大碉堡数
判断当前位置 是否可以放置碉堡，如果可以，放置碉堡并记录数量，继续遍历，然后回溯

由于遍历的顺序是从左到右、从上到下，因此每次判断当前位置是否可以放置碉堡时，只需要查看它的上方和左侧是否有碉堡 即可。

代码表示：

void Traversal(int dep, int num){
    // dep - 深度
    // num - 当前碉堡数
    if(dep == n * n){  // 达到右下角，更新碉堡数
        num_b = max(num_b, num);
        return ;
    }
    int x = dep / n;  // 当前行数
    int y = dep % n;  // 当前列数
    if(city[x][y] == '.' && isLegal(x, y)){  // 当前坐标可以放置
        city[x][y] = 'b';  // 放置碉堡
        Traversal(dep + 1, num + 1);  // 继续遍历
        city[x][y] = '.';  // 回溯
    }
    Traversal(dep + 1, num);  // 不能放置碉堡   
}

题解

#include <iostream>
#include <cmath>
using namespace std;

int s;
int m, n;

const double sqrt2 = sqrt(2.00);

int main(){
    cin>>s;  // 场景数
    int cnt = 1;  // 用于记录场景数
    while (s--){
        cin>>m>>n;
        cout<<"Scenario #"<<cnt<<":"<<endl;
        if(m%2==0 || n%2==0)  // m 和 n 中有一个是偶数
            printf("%.2lf\n", (double)(m * n));  // 一定可以通过贪吃蛇走法实现最短路线
        else
            printf("%.2lf\n", (double)(m * n - 1.00 + sqrt2));
        cout<<endl;
        cnt++;
    }
    

    return 0;
}