题目147：交叉格子中的长方形
Rectangles in cross-hatched gridsIn a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.
There are 5 grids smaller than 3x2, vertical and horizontal dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:
1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18
Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.
How many different rectangles could be situated within 47x43 and smaller grids?
题目：
在一个 3×2 的交叉格子中，一共可以找出 37 个矩形，如下图所示。
在区分横纵的情况下，小于 3×2 的格子一共有 5 个，1x1, 2x1, 3x1, 1x2 以及 2x2。如果将它们都用交叉线画成交叉格子，在它们内部分别可以找出如下数目的矩形：
1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18
将上面的数字与 3×2 中的 37 相加，可得在 3×2 以及更小的交叉格子中一共可以得到 72 个不同的矩形。
问，在 47×43 以及更小的交叉格子里，一共可以得到多少个不同的矩形？
正矩形数是85题对应的算法；斜矩形可以递推，但很麻烦，可以通过分析计算或找规律直接将m×n的网格里包含多少i×j的斜矩形个数的代数表达式写出来 import time
import math
timeStart = time.time()
m, n = 47, 43
def rect(m:int, n:int) -> int:
ans = m*(m+1)*n*(n+1)//4
for x in range(2, 2*min(m, n)+1):
row0 = (m-(x-1)//2)
col0 = (n-(x-1)//2)
row1 = (m-x//2)
col1 = (n-x//2)
y = (row0*col0 + row1*col1) * ((x-1)//2) + (row1*col0 + row0*col1) * (x//2)
ans += y
return ans
ans = 0
for i in range(1, m+1):
for j in range(1, n+1):
ans += rect(i, j)
print(ans)
print(f'time used: {time.time() - timeStart: .3f} s')
页:
[1]