题目147：交叉格子中的长方形

欧拉计划

Rectangles in cross-hatched grids

In 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的斜矩形个数的代数表达式写出来

瓦屋青衣

1. import time
   
2. import math
   
3. 
   
4. timeStart = time.time()
   
5. 
   
6. m, n = 47, 43
   
7. 
   
8. def rect(m:int, n:int) -> int:
   
9.     ans = m*(m+1)*n*(n+1)//4
   
10.     for x in range(2, 2*min(m, n)+1):
    
11.         row0 = (m-(x-1)//2)
    
12.         col0 = (n-(x-1)//2)
    
13.         row1 = (m-x//2)
    
14.         col1 = (n-x//2)
    
15.         y = (row0*col0 + row1*col1) * ((x-1)//2) + (row1*col0 + row0*col1) * (x//2)
    
16.         ans += y
    
17.     return ans
    
18. 
    
19. ans = 0
    
20. for i in range(1, m+1):
    
21.     for j in range(1, n+1):
    
22.         ans += rect(i, j)
    
23. print(ans)
    
24. 
    
25. print(f'time used: {time.time() - timeStart: .3f} s')

复制代码