UVA 11538 Chess Queen：計算兩皇后互相攻擊的放置方案數

題目大意

在一個 n × m 的棋盤上放置兩個不同的皇后，使得它們能夠互相攻擊。求共有多少種放置方法？

解題思路

皇后的攻擊範圍包含同行、同列與同對角線。將情況分為兩大類：

1. 同行或同列

先放第一個皇后，有 n × m 種選法。第二個皇后必須放在同行或同列，但不能重疊，因此有 (n - 1) + (m - 1) = n + m - 2 個可用位置。此類方案數為：

n * m * (n + m - 2)

2. 同對角線

考慮一個方向的對角線（另一個方向對稱，最後乘 2）。對角線長度分布為：
1, 2, 3, ..., n-1, n, n, ..., n, n-1, ..., 3, 2, 1（中間有 m + n - 1 條長度為 n 的對角線，假設 n ≤ m）。

若第一個皇后放在長度為 L 的對角線上，第二個皇后有 L - 1 個選擇。將所有對角線的 L × (L - 1) 求和，再乘 2（兩個對角線方向），可推導出封閉公式：

2 * n * (n - 1) * (3m - n - 1) / 3

最終公式

令 n ≤ m（否則交換），總方案數為：

ans = (m + n - 2) * n * m + 2 * n * (n - 1) * (3m - n - 1) / 3

參考代碼 (C++)

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    unsigned long long n, m;
    while (cin >> n >> m && (n || m)) {
        if (m < n) swap(n, m);
        unsigned long long ans = (m + n - 2) * n * m
                               + 2 * (n - 1) * n * (3 * m - n - 1) / 3;
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

時間複雜度 O(1)，空間複雜度 O(1)，適合大數據範圍。