我的算法书 - 教堂（church）

这本质是一个贪心题目, 没有下面说的那么复杂,你自己多画几个图,就可以发现不得不走斜边的情况: 奇数个点

这是一道经典的**网格图哈密顿回路（Grid Graph Hamiltonian Cycle）**问题的变种，结合了最短路径的计算。以下是对该题目的详细解析。

1. 题目分析

核心目标：在一个 $m \times n$ 的网格图中，从某一点出发，遍历每一个点（教堂）恰好一次，最后回到起点。我们需要求出这个回路的最短总长度。

移动规则与距离：每个点与周围 8 个方向相连（上、下、左、右、左上、右上、左下、右下）。

水平或垂直移动（正方向）：距离为 $1$ 。
对角线移动（斜方向）：根据勾股定理，距离为 $\sqrt{1^2+1^2} = \sqrt{2} \approx 1.41$ 。

为了使总路程最短，我们应该尽可能多地使用距离为 $1$ 的边（水平/垂直），尽量少用距离为 $\sqrt{2}$ 的边（对角线）。

2. 解题思路

我们可以根据网格中点的总数 $S = m \times n$ 的奇偶性来分类讨论。我们可以利用**国际象棋棋盘染色（奇偶性分析）**的方法来思考。

将网格看作国际象棋棋盘，相邻的（水平/垂直）格子颜色不同（黑白相间）。

水平/垂直移动：总是从黑格走到白格，或从白格走到黑格（改变颜色）。
对角线移动：总是从黑格走到黑格，或从白格走到白格（保持颜色不变）。

情况一： $m \times n$ 为偶数

如果网格点的总数是偶数，说明黑格和白格的数量相等。在二分图（网格图仅考虑正方向边时是二分图）中，如果节点数为偶数，通常存在一条哈密顿回路，只包含水平和垂直边。我们可以采用“蛇形走位”的方式遍历全图：例如 $2 \times 3$ 的网格： $(1,1) \to (1,2) \to (1,3) \to (2,3) \to (2,2) \to (2,1) \to (1,1)$ 这种路径只使用了水平和垂直边，没有使用对角线。

边的数量：遍历 $S$ 个点回到起点，需要走 $S$ 步。
最短距离： $S \times 1 = m \times n$ 。
样例验证：输入 2 3，总数 6，输出 6.00。符合公式。

情况二： $m \times n$ 为奇数

如果网格点的总数是奇数（意味着 $m$ 和 $n$ 都是奇数），黑格和白格的数量不等（例如黑格比白格多 1 个）。如果我们只使用水平/垂直移动（每次移动都改变颜色）：

第 1 步：黑 $\to$ 白
第 2 步：白 $\to$ 黑
…
第 $S$ 步（回到起点）：因为 $S$ 是奇数，第 $S$ 步应该走到白色格子。但我们的起点是黑色的。这意味着，仅凭奇数步的“变色移动”，无法回到同色的起点。

解决方案：为了解决这个奇偶性冲突，我们需要在路径中加入一步对角线移动（斜向）。

对角线移动不改变颜色（黑 $\to$ 黑），这相当于消耗了一步移动次数，但没有改变颜色的极性，从而修正了奇偶性，使得最后能回到起点。
为了距离最短，我们只需要1 步斜向移动，其余 $S-1$ 步全部用正向移动。
最短距离： $(S - 1) \times 1 + 1 \times \sqrt{2} = m \times n - 1 + \sqrt{2}$ 。

特殊情况： $m=1$ 或 $n=1$ （单行或单列）

虽然题目给出的范围较大且通常这类题目隐含 $m,n > 1$ 的矩形，但严谨起见需考虑线性情况。如果是 $1 \times n$ 的直线，要遍历所有点并回到起点，必须走到头再走回来。

路径： $1 \to 2 \to \dots \to n \to (n-1) \to \dots \to 1$ 。
距离： $(n-1)$ 去程 + $(n-1)$ 回程 = $2(n-1)$ 。 (注：绝大多数此类题目测试数据集中在 $m,n>1$ 的情况，但写代码时最好特判)

3. 算法总结

计算点总数 $S = m \times n$ 。
特判：如果 $m=1$ 或 $n=1$ ：
- 如果 $S=1$ ，距离为 0。
- 否则距离为 $2 \times (\max(m, n) - 1)$ 。
一般情况 ( $m, n > 1$ )：
- 如果 $S$ 是偶数：答案是 $S$ （即 double(m * n)）。
- 如果 $S$ 是奇数：答案是 $S - 1 + \sqrt{2}$ 。

4. C++ 代码实现

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

        #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm> // for max

using namespace std;

int main() {
    long long m, n; // 使用 long long 防止乘积溢出（虽然题目10000内int够用，但好习惯）
    if (cin >> m >> n) {
        // 特判线性情况 (m=1 或 n=1)
        if (m == 1 || n == 1) {
            if (m == 1 && n == 1) {
                printf("0.00\n");
            } else {
                long long len = max(m, n);
                printf("%.2f\n", (double)2 * (len - 1));
            }
        } 
        // 一般矩形情况
        else {
            long long total = m * n;
            if (total % 2 == 0) {
                // 偶数个点：全走直线
                printf("%.2f\n", (double)total);
            } else {
                // 奇数个点：走一步斜线，其余直线
                // 距离 = (Total - 1) * 1 + sqrt(2)
                printf("%.2f\n", (double)(total - 1) + sqrt(2));
            }
        }
    }
    return 0;
}

5. 关键点回顾

偶数点阵：可以通过蛇形填数形成闭环，全部由长度为 1 的边组成。
奇数点阵：由于二分图奇偶性限制，无法仅用长度为 1 的边形成闭环，必须借用至少一条长度为 $\sqrt{2}$ 的对角线边来“跳过”颜色的变换。

目录