第11题: 网格中的最大乘积

题目

网格中的最大乘积

在下面的$20 \times 20$网格中，对角线沿着的四个数字被标记为红色。

$$ 08\space 02\space 22\space 97\space 38\space 15\space 00\space 40\space 00\space 75\space 04\space 05\space 07\space 78\space 52\space 12\space 50\space 77\space 91\space 08 \\ 49\space 49\space 99\space 40\space 17\space 81\space 18\space 57\space 60\space 87\space 17\space 40\space 98\space 43\space 69\space 48\space 04\space 56\space 62\space 00 \\ 81\space 49\space 31\space 73\space 55\space 79\space 14\space 29\space 93\space 71\space 40\space 67\space 53\space 88\space 30\space 03\space 49\space 13\space 36\space 65 \\ 52\space 70\space 95\space 23\space 04\space 60\space 11\space 42\space 69\space 24\space 68\space 56\space 01\space 32\space 56\space 71\space 37\space 02\space 36\space 91 \\ 22\space 31\space 16\space 71\space 51\space 67\space 63\space 89\space 41\space 92\space 36\space 54\space 22\space 40\space 40\space 28\space 66\space 33\space 13\space 80 \\ 24\space 47\space 32\space 60\space 99\space 03\space 45\space 02\space 44\space 75\space 33\space 53\space 78\space 36\space 84\space 20\space 35\space 17\space 12\space 50 \\ 32\space 98\space 81\space 28\space 64\space 23\space 67\space 10\space \textcolor{red}{26}\space 38\space 40\space 67\space 59\space 54\space 70\space 66\space 18\space 38\space 64\space 70 \\ 67\space 26\space 20\space 68\space 02\space 62\space 12\space 20\space 95\space \textcolor{red}{63}\space 94\space 39\space 63\space 08\space 40\space 91\space 66\space 49\space 94\space 21 \\ 24\space 55\space 58\space 05\space 66\space 73\space 99\space 26\space 97\space 17\space \textcolor{red}{78}\space 78\space 96\space 83\space 14\space 88\space 34\space 89\space 63\space 72 \\ 21\space 36\space 23\space 09\space 75\space 00\space 76\space 44\space 20\space 45\space 35\space \textcolor{red}{14}\space 00\space 61\space 33\space 97\space 34\space 31\space 33\space 95 \\ 78\space 17\space 53\space 28\space 22\space 75\space 31\space 67\space 15\space 94\space 03\space 80\space 04\space 62\space 16\space 14\space 09\space 53\space 56\space 92 \\ 16\space 39\space 05\space 42\space 96\space 35\space 31\space 47\space 55\space 58\space 88\space 24\space 00\space 17\space 54\space 24\space 36\space 29\space 85\space 57 \\ 86\space 56\space 00\space 48\space 35\space 71\space 89\space 07\space 05\space 44\space 44\space 37\space 44\space 60\space 21\space 58\space 51\space 54\space 17\space 58 \\ 19\space 80\space 81\space 68\space 05\space 94\space 47\space 69\space 28\space 73\space 92\space 13\space 86\space 52\space 17\space 77\space 04\space 89\space 55\space 40 \\ 04\space 52\space 08\space 83\space 97\space 35\space 99\space 16\space 07\space 97\space 57\space 32\space 16\space 26\space 26\space 79\space 33\space 27\space 98\space 66 \\ 88\space 36\space 68\space 87\space 57\space 62\space 20\space 72\space 03\space 46\space 33\space 67\space 46\space 55\space 12\space 32\space 63\space 93\space 53\space 69 \\ 04\space 42\space 16\space 73\space 38\space 25\space 39\space 11\space 24\space 94\space 72\space 18\space 08\space 46\space 29\space 32\space 40\space 62\space 76\space 36 \\ 20\space 69\space 36\space 41\space 72\space 30\space 23\space 88\space 34\space 62\space 99\space 69\space 82\space 67\space 59\space 85\space 74\space 04\space 36\space 16 \\ 20\space 73\space 35\space 29\space 78\space 31\space 90\space 01\space 74\space 31\space 49\space 71\space 48\space 86\space 81\space 16\space 23\space 57\space 05\space 54 \\ 01\space 70\space 54\space 71\space 83\space 51\space 54\space 69\space 16\space 92\space 33\space 48\space 61\space 43\space 52\space 01\space 89\space 19\space 67\space 48 \\ $$

这些数字的乘积是$26 \times 63 \times 78 \times 14 = 1788696$。

在$20 \times 20$的网格中，同一方向（上、下、左、右或对角）的四个相邻数字的最大乘积是多少？

Largest Product in a Grid

In the $20 \times 20$ grid below, four numbers along a diagonal line have been marked in red.

$$ 08\space 02\space 22\space 97\space 38\space 15\space 00\space 40\space 00\space 75\space 04\space 05\space 07\space 78\space 52\space 12\space 50\space 77\space 91\space 08 \\ \vdots \\ 01\space 70\space 54\space 71\space 83\space 51\space 54\space 69\space 16\space 92\space 33\space 48\space 61\space 43\space 52\space 01\space 89\space 19\space 67\space 48 \\ $$

The product of these numbers is $26 \times 63 \times 78 \times 14 = 1788696$.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the $20 \times 20$ grid?

解题方法

循环遍历计算上、下、左、右、对角的值。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

std::uint32_t Product(const std::uint32_t grid[20][20]) {
    std::uint32_t result = 0;
    for (std::size_t i{ 0 }; i < 20; ++i) {
        for (std::size_t j{ 0 }; j < 20; ++j) {
            if (j <= 16) { // 右
                result = std::max(result, grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3]);
            }
            if (j >= 3) { // 左
                result = std::max(result, grid[i][j - 3] * grid[i][j - 2] * grid[i][j - 1] * grid[i][j]);
            }
            if (i <= 16) { // 下
                result = std::max(result, grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j]);
            }
            if (i >= 3) { // 上
                result = std::max(result, grid[i - 3][j] * grid[i - 2][j] * grid[i - 1][j] * grid[i][j]);
            }
            if (i <= 16 && j <= 16) { // 右下
                result = std::max(result, grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3]);
            }
            if (i >= 3 && j >= 3) { // 左上
                result = std::max(result, grid[i - 3][j - 3] * grid[i - 2][j - 2] * grid[i - 1][j - 1] * grid[i][j]);
            }
            if (i >= 3 && j <= 16) { // 右上
                result = std::max(result, grid[i - 3][j + 3] * grid[i - 2][j + 2] * grid[i - 1][j + 1] * grid[i][j]);
            }
            if (i <= 16 && j >= 3) { // 左下
                result = std::max(result, grid[i + 3][j - 3] * grid[i + 2][j - 2] * grid[i + 1][j - 1] * grid[i][j]);
            }
        }
    }
    return result;
}