ZOJ 1037 / HDU 1046 Gridland：找規律的幾何最短路徑

題目大意

在 n × m 的網格中，從左上角 (1,1) 出發，繞行所有格子最後回到起點，求最短路徑長度。移動只能上下左右，每步長 1。n, m ≤ 10000。

規律分析

• 若 n 或 m 為偶數：存在哈密頓回路，路徑長 = n × m（每格進出各一次）。
• 若 n 和 m 均為奇數：無哈密頓回路，必須有一步走對角線（長 √2），其余走直線。總長 = n×m - 1 + √2。

證理：棋盤染色，偶數格黑白相等可成環；奇數格黑白差 1，需一條對角線連接同色格。

代碼實現

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        double n, m; cin >> n >> m;
        cout << "Scenario #" << tc << ":\n";
        double ans;
        if ((long long)n % 2 == 0 || (long long)m % 2 == 0)
            ans = n * m;
        else
            ans = n * m - 1 + sqrt(2.0);
        cout << fixed << setprecision(2) << ans << "\n\n";
    }
    return 0;
}

注意點

• 輸入可能為浮點數格式（如 2.0），用 double 讀入再轉 long long 判斷奇偶。
• 輸出格式：Scenario #i: 獨佔一行，答案保留兩位小數，每組後空一行。
• sqrt(2.0) 需包含 ``。

總結

經典找規律題：網格圖哈密頓回路存在性取決於頂點數奇偶。奇×奇網格需引入一條對角線，長度增加 √2 - 1。屬於 ACM 入門必刷的數學規律題。