无法理解问题的要求。（ProjectEuler 问题：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?

in the same direction 和 up, down, left, right or diagonally 是什么意思？是我一个人还是这里的语言含糊不清？

这是我目前尝试过的方法：

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;

有了这个功能我满足了第一个需求但是上下左右还是对角？ or 是什么意思？

Answer 1

您需要检查 4 的每一行、每一列和对角线。这意味着您需要检查：

from grid[i-4][j] to grid[i][j]  
from grid[i][j-4] to grid[i][j]  
from grid[i-4][j-4] to grid[i][j] (diagonal) 
from grid[i+4][j-4] to grid[i][j] (other diagonal)

确保也要注意网格的两侧，就好像您在最左边一样，您需要向右看

Answer 2

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

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

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

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

你循环行
- 你循环列
  - 在当前点，你尝试获取4个值，包括当前点
    - 向下
    - 向右
    - right-downwards
    - right-upwards

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

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

我知道考虑这个部分解决方案比较困难，但如果您自己完成剩下的部分，那么从长远来看，它会对您有很大帮助运行，因为所有想法都在这里列出。

无法理解问题的要求。（ProjectEuler 问题：11）

Can't understand the requirement of the problem. (ProjectEuler problem: 11)

c

c++

algorithm

math

无法理解问题的要求。 （ProjectEuler 问题：11）

Can't understand the requirement of the problem. (ProjectEuler problem: 11)

c

c++

algorithm

math

无法理解问题的要求。（ProjectEuler 问题：11）