题目理解
1. 有一个 n 行 m 列的棋盘(格子是 1×1 的正方形)。
2. 求所有正方形的个数
3. 求所有长方形(不包括正方形)的个数
正方形个数
边长为 k 的正方形(k ≥ 1)在 n×m 的棋盘中的个数计算:
* 水平方向:可以放 (n - k + 1) 个起始行
* 垂直方向:可以放 (m - k + 1) 个起始列
可得:S = (n−k+1)×(m−k+1)
注意:k 的范围是 1 到 min(n, m)。
所有矩形数量计算:
R = n(n + 1) / 2 x m(m - 1) / 2
长方形个数:
长方形数 = R − S
样例验算(输入 2 3)
正方形:
k = 1:2 ×3 = 6
k = 2 : 1 x 2 = 2
合计:6 + 2 = 8
总矩形:
(2 x 3) / 2 x (3 x 4) / 2 = 3 x 6 = 18
长方形:
18 - 8 = 10