Не могу понять требования задачи. (проблема ProjectEuler: 11)
Я пытаюсь решить эту проблему: 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?
Это означает, что если вы проведете линию через четыре числа, все они должны быть рядом друг с другом на одной линии: горизонтальной, диагональной или вертикальной. Четыре цифры красного цвета дают пример «диагонали», и это может быть и диагональ Другие.
Ответы 2
Вам нужно проверить каждую строку, столбец и диагональ 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)
Обязательно следите за сторонами сетки, так как если вы находитесь в самом левом углу, вам нужно смотреть вправо.
Нужно проверить 8 вещей... в этом ответе только 4 из них
@SupportUkraine: проверка «a*b*c*d» аналогична проверке «d*c*b*a». ИМХО проверять 4 товара проще, чем проверять 8 :) ... и это позволяет избежать повторений
@SupportUkraine: Остальные 4 одинаковы, за исключением краев, поскольку вы находите произведение (которое является коммутативным). смотреть назад на 4 шага эквивалентно тому, чтобы смотреть вперед на 4 шага, когда 4 шага позади.
@pmg Нет, это разные числа. вверх, вниз, влево, вправо и 4 разные диагонали
@SupportUkraine ... i2.paste.pics/4fcd98f5fc4bd993614eeac97cccb0f5.png
Это вопрос алгоритма: не проверять один набор, когда вы уже проверили его с другого конца.
@pmg На вашей картинке отсутствует другая диагональ. Для данного элемента сетки существует 8 значений. Вы можете оптимизировать программу, используя это для того, чтобы верхнее значение для одного элемента сетки было таким же, как нижнее значение для другого элемента сетки, но это уже другая история.
@SupportUkraine нет, не пропало. В основном есть четыре линии, пересекающие данную точку. Можно выбрать проверку только четырех строк при зацикливании сетки. Этот ответ правильный.
@LajosArpad Нет, это не так. И это даже не ответ на вопрос
@SupportUkraine, поскольку вопрос был о понимании того, что означает направление в сетке, технически он отвечает на вопрос, поэтому я проголосовал за этот ответ.
@LajosArpad Мы можем согласиться с вопросом ... но нет, этот ответ неверен. Для каждого элемента сетки необходимо учитывать 8 значений. Да, вы можете сделать лучшую реализацию, чем перебирать все элементы сетки и каждый раз вычислять 8 значений, но это не вопрос.
@SupportUkraine давайте рассмотрим пункт (4, 4). Я полагаю, что под 8 строками вы имеете в виду (1, 1)-(4,4), (4, 4)-(7,7), (1, 4)-(4, 4), (4, 4) -(7, 4), (4, 1)-(4, 4), (4, 4)-(4, 7), (1, 7)-(4, 4) и (4, 4)-( 7, 1). Я перечислил их, чтобы убедиться, что мы находимся на одной странице. Теперь я говорю, что когда мы находимся в (4, 4), например, мы учитываем (4, 4)-(7, 7), но мы не принимаем во внимание (1, 1)-(4, 4) в этот момент, потому что этот случай уже был учтен на более ранней стадии цикла, когда мы находимся в точке (1, 1).
@SupportUkraine Итак, если мы примем во внимание (r, c), (r + 1, c + 1), (r + 2, c + 2), (r + 3, c + 3) как направление, когда мы в (r, c), но мы не учитываем отрицательное в этой точке, то ничего не упускаем, потому что, когда мы были в (r - 3, c -3), то мы уже учли направление, о котором вы говорили.
@LajosArpad Полностью согласен с тем, что вы можете делать такие оптимизации, но вопрос не в этом. Такие ответы только еще больше запутают
@LajosArpad Ответ здесь i.stack.imgur.com/RmdBj.png OP, спросите, что означает текст, и вот что он означает. ОП не спрашивает о лучшей реализации
Направление в контексте сетки — это геометрическое пространство, все точки которого лежат на одной линии.
Если взять точку, то мы можем пересечь ее 4 разными линиями:
\ | /
\ | /
\ | /
\|/
----*----
/|\
/ | \
/ | \
/ | \
Итак, как мы можем определить эти направления? Есть очень простой способ сделать это:
- вы зацикливаете ряды
- вы зацикливаете столбцы
- в текущей точке вы пытаетесь получить 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и 0rowDir - 2: наличие 1
colDirи 1rowDir - 3: наличие 1
colDirи -1rowDir
- 1: наличие 1
Я знаю, что рассмотреть это частичное решение труднее, но в долгосрочной перспективе это очень поможет вам, если вы сделаете все остальное самостоятельно, так как все идеи изложены здесь.
upиdownодинаковы;leftиrightодинаковы;diagonallyможет быть как / или \. Всего нужно протестировать 4 направления.