0011. 方阵最大乘积
* * * *
拉格朗日计划
* * * *
方阵最大乘积

在如下的$20\times20$的方阵中,有四个呈对角线排列的数被标记为红色: $$\begin{matrix} 08 & 02 & 22 & 97 & 38 & 15 & 00 & 40 & 00 & 75 & 04 & 05 & 07 & 78 & 52 & 12 & 50 & 77 & 91 & 08 \\ 49 & 49 & 99 & 40 & 17 & 81 & 18 & 57 & 60 & 87 & 17 & 40 & 98 & 43 & 69 & 48 & 04 & 56 & 62 & 00 \\ 81 & 49 & 31 & 73 & 55 & 79 & 14 & 29 & 93 & 71 & 40 & 67 & 53 & 88 & 30 & 03 & 49 & 13 & 36 & 65 \\ 52 & 70 & 95 & 23 & 04 & 60 & 11 & 42 & 69 & 24 & 68 & 56 & 01 & 32 & 56 & 71 & 37 & 02 & 36 & 91 \\ 22 & 31 & 16 & 71 & 51 & 67 & 63 & 89 & 41 & 92 & 36 & 54 & 22 & 40 & 40 & 28 & 66 & 33 & 13 & 80 \\ 24 & 47 & 32 & 60 & 99 & 03 & 45 & 02 & 44 & 75 & 33 & 53 & 78 & 36 & 84 & 20 & 35 & 17 & 12 & 50 \\ 32 & 98 & 81 & 28 & 64 & 23 & 67 & 10 & \textcolor{red}{26} & 38 & 40 & 67 & 59 & 54 & 70 & 66 & 18 & 38 & 64 & 70 \\ 67 & 26 & 20 & 68 & 02 & 62 & 12 & 20 & 95 & \textcolor{red}{63} & 94 & 39 & 63 & 08 & 40 & 91 & 66 & 49 & 94 & 21 \\ 24 & 55 & 58 & 05 & 66 & 73 & 99 & 26 & 97 & 17 & \textcolor{red}{78} & 78 & 96 & 83 & 14 & 88 & 34 & 89 & 63 & 72 \\ 21 & 36 & 23 & 09 & 75 & 00 & 76 & 44 & 20 & 45 & 35 & \textcolor{red}{14} & 00 & 61 & 33 & 97 & 34 & 31 & 33 & 95 \\ 78 & 17 & 53 & 28 & 22 & 75 & 31 & 67 & 15 & 94 & 03 & 80 & 04 & 62 & 16 & 14 & 09 & 53 & 56 & 92 \\ 16 & 39 & 05 & 42 & 96 & 35 & 31 & 47 & 55 & 58 & 88 & 24 & 00 & 17 & 54 & 24 & 36 & 29 & 85 & 57 \\ 86 & 56 & 00 & 48 & 35 & 71 & 89 & 07 & 05 & 44 & 44 & 37 & 44 & 60 & 21 & 58 & 51 & 54 & 17 & 58 \\ 19 & 80 & 81 & 68 & 05 & 94 & 47 & 69 & 28 & 73 & 92 & 13 & 86 & 52 & 17 & 77 & 04 & 89 & 55 & 40 \\ 04 & 52 & 08 & 83 & 97 & 35 & 99 & 16 & 07 & 97 & 57 & 32 & 16 & 26 & 26 & 79 & 33 & 27 & 98 & 66 \\ 88 & 36 & 68 & 87 & 57 & 62 & 20 & 72 & 03 & 46 & 33 & 67 & 46 & 55 & 12 & 32 & 63 & 93 & 53 & 69 \\ 04 & 42 & 16 & 73 & 38 & 25 & 39 & 11 & 24 & 94 & 72 & 18 & 08 & 46 & 29 & 32 & 40 & 62 & 76 & 36 \\ 20 & 69 & 36 & 41 & 72 & 30 & 23 & 88 & 34 & 62 & 99 & 69 & 82 & 67 & 59 & 85 & 74 & 04 & 36 & 16 \\ 20 & 73 & 35 & 29 & 78 & 31 & 90 & 01 & 74 & 31 & 49 & 71 & 48 & 86 & 81 & 16 & 23 & 57 & 05 & 54 \\ 01 & 70 & 54 & 71 & 83 & 51 & 54 & 69 & 16 & 92 & 33 & 48 & 61 & 43 & 52 & 01 & 89 & 19 & 67 & 48 \end{matrix}$$ 这四个数的乘积是$26\times63\times78\times14=1788696$。在这个$20\times20$的方阵中,四个相邻且呈一直线(竖直、水平或对角线)排列的数的乘积最大是多少?

本题难度:



解答

从左上角起遍历,每次从左侧、下方、左下、右下再取$3$个元素相乘依次比较即可,结果是$70600674=89\times94\times97\times87$ (系从左上角数起第$13$行与第$7$列相交处向左下方再取$3$个数)。

theList=[[..],[..]] #将上述方针以二维数组形式保存在theList中,数据太长此处略去
  
theMax=0
rowPos=0
colPos=0
g=0 #0,1,2,3 分别表示右、下、左下、右下

for i in range(20):
    for j in range(20):
        if j<17:
            h=theList[i][j]*theList[i][j+1]*theList[i][j+2]*theList[i][j+3]
            if h>theMax:
                theMax=h
                colPos=j
                rowPos=i
                g=0
        if i<17:
            v=theList[i][j]*theList[i+1][j]*theList[i+2][j]*theList[i+3][j]
            if v>theMax:
                theMax=v
                colPos=j
                rowPos=i
                g=1
        if i<17 and j>2:
            ld=theList[i][j]*theList[i+1][j-1]*theList[i+2][j-2]*theList[i+3][j-3]
            if ld>theMax:
                theMax=ld
                colPos=j
                rowPos=i
                g=2
        if i<17 and j<17:
            rd=theList[i][j]*theList[i+1][j+1]*theList[i+2][j+2]*theList[i+3][j+3]
            if rd>theMax:
                theMax=rd
                colPos=j
                rowPos=i
                g=3

print theMax,rowPos+1,colPos+1,g