C++棋盘正方形与长方形计数：公式推导与代码实现

这个问题是经典的**棋盘计数问题**，用数学公式即可高效解决，无需模拟遍历（暴力枚举复杂度O(N²M²)也能过，因为N、M都≤100，但公式法是O(1)）。 ## 🧮 核心数学原理 在 `N×M` 的网格中： - **正方形个数**： 遍历边长 `k`（从 1 到 `min(N, M)`），每个边长为 `k` 的正方形数量为 `(N - k + 1) × (M - k + 1)`，累加。 \[ \text{正方形总数} = \sum_{k=1}^{\min(N,M)} (N-k+1)(M-k+1) \] - **长方形（包括正方形）总个数**： 任意选择一个矩形，需要选两条水平线和两条竖直线。 在 `N` 条水平线中选 2 条：`C(N+1, 2) = N(N+1)/2` 在 `M` 条竖直线中选 2 条：`M(M+1)/2` 两者相乘得到**所有矩形（含正方形）总数**。 - **长方形（不包括正方形）个数**： 用总矩形数减去正方形数。 --- ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int N, M; cin >> N >> M; // 计算正方形总数 long long squares = 0; int minNM = min(N, M); for (int k = 1; k <= minNM; ++k) { squares += (long long)(N - k + 1) * (M - k + 1); } // 计算所有矩形（含正方形）总数 long long totalRectangles = (long long)N * (N + 1) / 2 * M * (M + 1) / 2; // 长方形（不含正方形） long long rectangles = totalRectangles - squares; cout << squares << "," << rectangles << endl; return 0; } ``` --- ## 📊 代码解析 - **`minNM = min(N, M)`**：正方形最大边长不能超过棋盘短边。 - **循环累加**：每次计算边长为 `k` 的正方形数量，注意乘数都要转换为 `long long`，避免 `int` 溢出（N、M最大100，直接算也安全，但用 `long long` 更稳健）。 - **总矩形公式**： `N * (N+1) / 2` 表示在 N 行网格中选上下两条水平线的组合数，`M` 同理。两者乘积即为所有矩形数。 - **最终输出**：`squares` 和 `rectangles` 用逗号分隔，与题目输出格式一致。 --- ## ⚠️ 注意事项 1. **数据类型**：虽然本题 N、M ≤ 100，最大结果在 10^8 量级，`int` 可能勉强放下，但推荐用 `long long` 防止边界情况。 2. **输入格式**：题目示例用逗号分隔输入（`3,2`），但实际 OJ 通常用空格或换行，**建议直接用 `cin >> N >> M`**，它天然支持空格/换行，也能支持逗号？——不，逗号会读取失败。保险起见，如果输入是逗号，需要特殊处理。但绝大多数 OJ 用空格。 3. **公式正确性**：这是经典的排列组合计数，务必记住“选线”思想，而不是模拟每个格子。 --- ## 🔧 扩展思考 - **如果棋盘是带障碍的**，就不能用公式，需要动态规划或扫描线法。 - **如果只问正方形**，上述循环是标准解法，也可以直接公式求和。 - **如果 N 和 M 特别大（>10^7）**，循环依然适用，但注意结果可能要用大数（如 `__int128` 或高精度）。 --- ## 📚 推荐的学习资源 - [组合计数基础（OI Wiki）](https://oi-wiki.org/math/combinatorics/) - [LeetCode 221. 最大正方形](https://leetcode.cn/problems/maximal-square/)（动态规划版正方形计数） - 《算法竞赛入门经典》第二版，组合数学章节 ######[AI写代码神器 | 989点数解答 | 2026-08-28 20:46:25]