086. 长方体路线(Cuboid route)

一个蜘蛛S位于大小为6乘5乘3的长方体房间的一角,而一只苍蝇F则位于对角。通过在房间的表面上移动,从S到F的最短“直线”距离为10,该路径已经在图中标示出来了。

img

但是,对于任何给定的长方体,最多有三个“最短”路径候选,并且最短路径并不总是具有整数长度。可以发现,在不考虑旋转的情况下,具有整数维度且最大尺寸为\(M\times M \times M\)的长方体中,如果\(M=100\),那么最短路径恰好为整数的长方体有\(2060\)个。它是整数最短路径数量首次超过\(2000\)的最小的\(M\)值,当\(M=99\)时,整数最短路径有\(1975\)个。

求使得整数最短路径的数量首次超过一百万的\(M\)的最小值。

分析:首先我们可以分析一下如何计算经过长方体表面,两个对角顶点的的最短路径。乍看起来像一个立体几何问题,但实际上我们只有把长方体看成一个纸盒,然后把这个纸盒摊成一个平面,这个最短路径很容易就可以看出来了,如下:

img

这是把题目中展示的长方体展开成平面的样子,假如我们从\(A\)点出发,要到达对角顶点,实际就是要到达\(H,M,E\)这三个顶点,因为当把盒子折起来之后,这三个点会重合成一个点。所以题目中的问题可以转化为在如上的平面图中,连接\(A\)点与\(H,M,E\)三点中的最短线段,显然在图中这个最短线段就是\(AH\),它是直角三角形\(HBA\)的斜边,因此其长度:

$$ AH^2=AB^2+HB^2=6^2+(3+5)^2=6^2+8^2=100\Rightarrow AH=10 $$

对其它尺寸的长方体,我们可以采用类似的思路。因为题目明确不考虑长方体旋转产生的差异,所以不失一般性,我们可以设长方体最长的边为\(length\),次长的边为\(width\),最短的边为\(height\),则有\(M\ge length\ge width \ge height \ge1\),则此时经过长方体表面连接对角顶点的最短距离\(d_{min}=\sqrt{length^2+(width+height)^2}\),我们的目标是确保\(d_{min}\)是一个整数。为简化问题,我们可以进一步设\(wph=width+height\),显然有:

$$ 1\le length \le M,2\le wph\le2*length $$

则问题转化为在给定\(length\)的情况下,有多少个\(width\)\(height\)的组合使得\(d_{min}\)为整数,则假设\(d_{min}\)为整数,我们可以根据此时的\(length\)\(wph\),求出\(width\)\(height\)的组合个数,需要分两种情况讨论,如下图:

img

第一种情况是\(length<wph\),因为我们要求\(length\ge width \ge height\),所以\(width\)的最小值应该是\(wph\)的一半,最大值应该是\(length\),则区间内的整数个数有\(length-(wph+1)/2+1\)个。第二种情况是\(length>wph\),则\(width\)的最小值为\(wph/2\),最大值为\(wph\),则区间范围内的整数个数有\(wph/2\)个。

根据以上条件,我们就可以求出满足题目要求的整数最短路径数量的个数,代码如下:

# time cost = 3.85 s ± 3.71 ms

def main(N=10**6):
    c,length = 0,1
    while c < N:
        length = length + 1
        for wph in range(3,2*length):
            sq = (length**2 + wph**2)**0.5
            if sq % 1 == 0:
                c += (wph//2) if length>wph else (length-(wph+1)//2+1)
    return length