147. 交叉网格中的矩形(Rectangles in Cross-hatched Grids)
在一个 \(3 \times 2\) 的交叉网格（每个单位方格内都画有两条对角线）中，共有 \(37\) 个不同的矩形可以放置在该网格内（如题图所示）。
有 \(5\) 个比 \(3 \times 2\) 更小的网格（水平和垂直维度是有区别的），即 \(1 \times 1\)、\(2 \times 1\)、\(3 \times 1\)、\(1 \times 2\) 和 \(2 \times 2\)。如果每个网格都是交叉网格，那么在这些较小网格中可以放置以下数量的不同矩形：
\(1 \times 1\) \(1\) \(2 \times 1\) \(4\) \(3 \times 1\) \(8\) \(1 \times 2\) \(4\) \(2 \times 2\) \(18\) 将这些数字与 \(3 \times 2\) 网格的 \(37\) 相加，在 \(3 \times 2\) 及更小的所有网格中共有 \(72\) 个不同的矩形。
在 \(47 \times 43\) 及更小的所有网格中，共有多少个不同的矩形？
一、数学背景
交叉网格（cross-hatched grid）是在标准矩形网格的基础上，在每个单位方格内画出两条对角线的图形。题目要求计算在这些线条（水平线、竖直线、对角线）上能够形成的所有矩形数量。
分析矩形的构成：矩形的四条边必须沿着网格中已有的线段。由于矩形四个角均为 \(90^\circ\)，只有以下两种类型的矩形：
- 轴对齐矩形：对边分别平行于 \(x\) 轴和 \(y\) 轴，即边落在水平线和竖直线上。
- 对角矩形：对边分别沿 \(45^\circ\) 和 \(-45^\circ\) 方向，即边落在两类对角线上。
不存在混合类型（例如两边水平、两边对角），因为那样角度不是 \(90^\circ\)。
二、算法设计
轴对齐矩形
对于 \(a \times b\) 的网格，有 \((a+1)\) 条水平线和 \((b+1)\) 条竖直线。轴对齐矩形由选择 \(2\) 条水平线和 \(2\) 条竖直线确定，数量为：
对角矩形
设网格大小为 \(a \times b\)（\(a\) 行，\(b\) 列）。两类对角线方程分别为：
- \(/\) 线：\(y = x + k\)，其中 \(k \in \{-(b-1), \dots, a-1\}\)，共 \(a+b-1\) 条
- \(\backslash\) 线：\(y = -x + l\)，其中 \(l \in \{1, \dots, a+b-1\}\)，共 \(a+b-1\) 条
对角矩形由选择 \(k_1 < k_2\) 和 \(l_1 < l_2\) 确定，四个顶点位于对应直线的交点处。矩形要完全位于 \([0, b] \times [0, a]\) 网格内，四个顶点的坐标约束等价于：
给定 \((k_1, k_2)\) 后，\(l_1\) 有效下界为 \(\max(1, k_2, -k_1)\)，\(l_2\) 有效上界为 \(\min(a+b-1, 2a-k_2, 2b+k_1)\)。对满足 \(l_1 < l_2\) 的组合计数即可。
最终答案
对所有 \(1 \le a \le 47\)、\(1 \le b \le 43\) 求和：
三、复杂度分析
- 共 \(47 \times 43 = 2021\) 个 \((a,b)\) 对
- 每个 \((a,b)\) 对需要遍历约 \((a+b)^2/2\) 个 \((k_1, k_2)\) 组合，每个组合 \(O(1)\) 计算 \(l\) 对数量
- 最大 \(a+b \approx 90\)，最坏情况下单对约 \(4000\) 次迭代
- 总操作量约 \(8 \times 10^6\) 次整数运算，Python 实现运行时间 \(< 1\) 秒
四、代码实现与说明
"""Project Euler Problem 147: Rectangles in Cross-hatched Grids"""
def count_diagonal_rectangles(a, b):
"""
Count the number of diagonal (45-degree rotated) rectangles that can be
situated within an a x b cross-hatched grid.
The grid has a rows (y direction) and b columns (x direction) of unit squares.
Diagonal lines of two families are drawn:
"/" lines: y = x + k, for k in [-(b-1), a-1] (total a+b-1 lines)
"\" lines: y = -x + l, for l in [1, a+b-1] (total a+b-1 lines)
A diagonal rectangle is determined by choosing k1 < k2 and l1 < l2
such that all 4 vertices lie within the grid bounds [0,b] x [0,a].
"""
u_min = -(b - 1) # minimum k ("/" line index)
u_max = a - 1 # maximum k
v_min = 1 # minimum l ("\" line index)
v_max = a + b - 1 # maximum l
total = 0
for u1 in range(u_min, u_max + 1):
for u2 in range(u1 + 1, u_max + 1):
# Lower bound on l1: it must be >= u2 (x>=0), >= -u1 (y>=0), >= 1
l1_low = max(v_min, u2, -u1)
# Upper bound on l2: <= 2a - u2 (y<=a), <= 2b + u1 (x<=b), <= v_max
l2_high = min(v_max, 2 * a - u2, 2 * b + u1)
if l1_low >= l2_high:
continue # no valid l1 < l2 pairs
# l1 valid range: [l1_low, min(v_max, l2_high - 1)]
l1_max = min(v_max, l2_high - 1)
M = min(v_max, l2_high) # effective upper bound for l2
n_l1 = l1_max - l1_low + 1
# sum_{l1=l1_low}^{l1_max} (M - l1)
# = n_l1 * M - n_l1 * (l1_low + l1_max) // 2
count = n_l1 * M - n_l1 * (l1_low + l1_max) // 2
total += count
return total
def count_rectangles(a, b):
"""Count all rectangles (axis-aligned + diagonal) in an a x b cross-hatched grid."""
# Axis-aligned: choose 2 of (a+1) horizontal lines and 2 of (b+1) vertical lines
axis = (a * (a + 1) * b * (b + 1)) // 4
diagonal = count_diagonal_rectangles(a, b)
return axis + diagonal
def solve(m=47, n=43):
"""
Sum the number of rectangles over all a x b cross-hatched grids
where 1 <= a <= m and 1 <= b <= n.
"""
total = 0
for a in range(1, m + 1):
for b in range(1, n + 1):
total += count_rectangles(a, b)
return total
if __name__ == "__main__":
# Test with sample: 3x2 and smaller should give 72
sample = solve(m=3, n=2)
print(f"Sample (3x2 and smaller): {sample} (expected 72)")
assert sample == 72, f"Sample failed: got {sample}"
# Run for the actual problem
answer = solve(m=47, n=43)
print(f"Answer (47x43 and smaller): {answer}")
count_diagonal_rectangles 函数
- 给定网格尺寸 \(a \times b\)，定义两类对角线：
/线 \(y = x + k\)（\(k \in [-(b-1), a-1]\)）和\线 \(y = -x + l\)（\(l \in [1, a+b-1]\)）。 - 对角矩形由选择 \(k_1 < k_2\) 和 \(l_1 < l_2\) 确定，四个顶点位于对应直线交点。
- 对每对 \((k_1, k_2)\)，通过四个边界条件计算 \(l_1\) 的下界和 \(l_2\) 的上界：
- \(l_1 \ge \max(1, k_2, -k_1)\)（左侧与底部不越界）
- \(l_2 \le \min(a+b-1, 2a-k_2, 2b+k_1)\)（右侧与顶部不越界）
- 利用等差数列求和公式在 \(O(1)\) 内计算满足 \(l_1 < l_2\) 的 \((l_1, l_2)\) 对数，避免三层循环。
count_rectangles 函数
- 轴对齐矩形数由组合公式 \(\binom{a+1}{2} \binom{b+1}{2}\) 直接给出。
- 对角矩形数调用
count_diagonal_rectangles计算。 - 两者相加得到单个网格的矩形总数。
solve 函数
- 对 \(1 \le a \le m\)、\(1 \le b \le n\) 的所有网格求和，得到最终答案。
- 主入口先以 \(m=3, n=2\) 验证样例输出 \(72\)，再以 \(m=47, n=43\) 计算最终结果。