c++ - 无法理解问题的要求。 (欧拉项目问题: 11)

Question

我正在尝试解决这个问题:https://projecteuler.net/problem=11 然而，这部分让我感到困惑:

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

同向和上、下、左、右或对角线是什么意思？ 是我的问题还是这里的语言含糊不清？

这是我迄今为止尝试过的:

long int prod{0}, n{20};

for(int i{0}; i <= n; i++) {
    for(int j{0}; j <= n; j++) {
        long int a{grid[i][j]}, b{grid[i+1][j+1]}, c{grid[i+2][j+2]}, d{grid[i+3][j+3]};
        if(prod < (a * b * c * d))
            prod = a * b * c * d;
    }
}

return prod;

通过这个函数我满足了第一个需求，但是上下左右还是对角线？ 或是什么意思？

Answer 1

网格上下文中的方向是所有点都在同一条线上的几何空间。

如果我们取一个点，那么我们可以用 4 条不同的线穿过它:

\   |   /
 \  |  /
  \ | /
   \|/
----*----
   /|\
  / | \
 /  |  \
/   |   \

那么，我们如何定义这些方向呢？有一个非常简单的方法:

• 循环行
  • 循环列
    • 在当前点，您尝试获取 4 个值，包括当前点
      • 向下
      • 向右
      • 右下
      • 从右向上

我说“尝试”，这意味着由于网格的边界，您将不得不忽略相当多的可能性。然而，这是获取所有四个方向的巧妙方法:

int bestProduct = -1; //Assuming you have positives
for (int row = 0; row < n; row++) {
    for (int column = 0; column < n; column++) {
        int ignore = 0;
        int rowDir = 0;
        int colDir = 1;
        int product = grid[row][column];
        for (int index = 0; (!ignore) && (index < 3); index++) {
            if (
                   (row + rowDir < 0) ||
                   (row + rowDir >= n) ||
                   (column + colDir < 0) ||
                   (column + colDir >= m)
               ) {
                ignore = 1;
            }
            else product *= grid[row + rowDir][column + colDir];
        }
        if ((!ignore) && (bestProduct < product)) bestProduct = product;
    }
}

这不是完整的实现，因为您还需要做一些工作。您需要继续:

• 将第二个循环的内部部分转换为除 if 条件之外的函数，用于检查产品是否高于迄今为止的最佳产品
• 删除内部代码并将其替换为函数调用
• 再调用该函数三次，每次为彼此方向
• 其他方向是:
  • 1:有 1 个 colDir 和 0 rowDir
  • 2:有 1 个 colDir 和 1 个 rowDir
  • 3:有 1 colDir 和 -1 rowDir

我知道考虑这个部分解决方案比较困难，但从长远来看，如果您自己完成其余部分，它将对您有很大帮助，因为这些想法都在这里列出。