Крупнейший продукт в сетке «Не в том же направлении»

https://projecteuler.net/problem=11 Вот вопрос:

int grid[20][20] = 
    {
        {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
        {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
        {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
        {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
        {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
        {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
        {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
        {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
        {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
        {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
        {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
        {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
        {4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
        {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
        {4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
        {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
        {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
        {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}
    };

Каково наибольшее произведение четырех соседних чисел в «одном направлении» (вверх, вниз, влево, вправо или по диагонали) в сетке 20 на 20? Сначала я неправильно прочитал вопрос и не увидел части «в том же направлении». Я думал, что правило заключается в том, что каждое число должно быть соседним хотя бы с одним другим числом в сетке, а не максимум.

Мне удалось решить эту проблему довольно быстро (я также использовал

Решение:

#include <stdio.h>

// Function to find the maximum product of four adjacent numbers in a grid
int findMaxProduct(int grid[20][20], int* pos)
{
    int maxProduct = 0;

    // Check horizontally
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 20 - 3; j++)
        {
            int product = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3];
            printf("Checking horizontally at (%d, %d) -> product: %d\n", i, j, product);
            if (product > maxProduct)
            {
                maxProduct = product;
                pos[0] = i; pos[1] = j;
                pos[2] = i; pos[3] = j + 1;
                pos[4] = i; pos[5] = j + 2;
                pos[6] = i; pos[7] = j + 3;
                printf("New max horizontal product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
                       maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
            }
        }
    }

    // Check vertically
    for (int i = 0; i < 20 - 3; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            int product = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j];
            printf("Checking vertically at (%d, %d) -> product: %d\n", i, j, product);
            if (product > maxProduct)
            {
                maxProduct = product;
                pos[0] = i; pos[1] = j;
                pos[2] = i + 1; pos[3] = j;
                pos[4] = i + 2; pos[5] = j;
                pos[6] = i + 3; pos[7] = j;
                printf("New max vertical product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
                       maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
            }
        }
    }

    // Check diagonally (down-right)
    for (int i = 0; i < 20 - 3; i++)
    {
        for (int j = 0; j < 20 - 3; j++)
        {
            int product = grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3];
            printf("Checking diagonally down-right at (%d, %d) -> product: %d\n", i, j, product);
            if (product > maxProduct)
            {
                maxProduct = product;
                pos[0] = i; pos[1] = j;
                pos[2] = i + 1; pos[3] = j + 1;
                pos[4] = i + 2; pos[5] = j + 2;
                pos[6] = i + 3; pos[7] = j + 3;
                printf("New max diagonal down-right product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
                       maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
            }
        }
    }

    // Check diagonally (down-left)
    for (int i = 0; i < 20 - 3; i++)
    {
        for (int j = 3; j < 20; j++)
        {
            int product = grid[i][j] * grid[i + 1][j - 1] * grid[i + 2][j - 2] * grid[i + 3][j - 3];
            printf("Checking diagonally down-left at (%d, %d) -> product: %d\n", i, j, product);
            if (product > maxProduct)
            {
                maxProduct = product;
                pos[0] = i; pos[1] = j;
                pos[2] = i + 1; pos[3] = j - 1;
                pos[4] = i + 2; pos[5] = j - 2;
                pos[6] = i + 3; pos[7] = j - 3;
                printf("New max diagonal down-left product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
                       maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
            }
        }
    }

    return maxProduct;
}

int main(void)
{
    int grid[20][20] = 
    {
        {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
        {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
        {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
        {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
        {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
        {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
        {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
        {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
        {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
        {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
        {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
        {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
        {4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
        {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
        {4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
        {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
        {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
        {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}
    };

    int pos[8]; // To store the positions of the 4 adjacent numbers with the highest product
    int maxProduct = findMaxProduct(grid, pos);

    printf("The maximum product of four adjacent numbers is %d.\n", maxProduct);
    printf("The positions of these numbers are:\n");
    for (int i = 0; i < 8; i += 2)
    {
        printf("(%d, %d)\n", pos[i], pos[i + 1]);
    }

    return 0;
}

Что, если мы рассмотрим числа, расположенные в разных направлениях? Единственное правило заключается в том, что каждое число должно быть смежным хотя бы с одним другим числом, а не только с одним другим числом. Как будто сам ответ может состоять из 4 чисел, которые примыкают друг к другу, как квадратная матрица 2 на 2?

Теперь нам предстоит искать гораздо больше вещей. Поиск фигур в Python вручную

def is_in_bounds(x, y, rows, cols):
    return 0 <= x < rows and 0 <= y < cols

def generate_combinations(x, y):
    return 
    [
        [(x, y), (x+1, y), (x+2, y), (x+3, y)],  # Horizontal line
        [(x, y), (x, y+1), (x, y+2), (x, y+3)],  # Vertical line
        [(x, y), (x+1, y+1), (x+2, y+2), (x+3, y+3)],  # Diagonal down-right
        [(x, y), (x-1, y+1), (x-2, y+2), (x-3, y+3)],  # Diagonal down-left
        [(x, y), (x+1, y), (x, y+1), (x+1, y+1)],  # 2x2 square
        [(x, y), (x+1, y), (x+2, y), (x+2, y+1)],  # L-shape 1
        [(x, y), (x, y+1), (x, y+2), (x+1, y+2)],  # L-shape 2
        [(x, y), (x+1, y), (x+2, y), (x, y+1)],  # L-shape 3
        [(x, y), (x, y+1), (x, y+2), (x+1, y)],  # L-shape 4
        [(x, y), (x+1, y), (x+2, y), (x+1, y+1)],  # T-shape 1
        [(x, y), (x, y+1), (x, y+2), (x+1, y+1)],  # T-shape 2
        [(x, y), (x+1, y), (x+1, y+1), (x+1, y+2)],  # T-shape 3
        [(x, y), (x, y+1), (x-1, y+1), (x+1, y+1)]  # T-shape 4
    ]

def calculate_product(grid, combination):
    product = 1
    for x, y in combination:
        product *= grid[x][y]
    return product

def find_max_product(grid):
    max_product = 0
    max_combination = []
    rows = len(grid)
    cols = len(grid[0])
    
    for i in range(rows):
        for j in range(cols):
            combinations = generate_combinations(i, j)
            valid_combinations = [comb for comb in combinations if all(is_in_bounds(x, y, rows, cols) for x, y in comb)]
            
            for comb in valid_combinations:
                product = calculate_product(grid, comb)
                print(f"Combination: {comb} => Values: {[grid[x][y] for x, y in comb]} => Product: {product}")
                
                if product > max_product:
                    max_product = product
                    max_combination = comb
    
    print(f"Max product combination: {max_combination} => Product: {max_product}")
    return max_product

# Example usage
grid = [[int(x) for x in line.split()] for line in """
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 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 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
""".strip().split('\n')]

print(find_max_product(grid))

Но если задача требует n=5; Мне нужно будет вручную найти больше фигур на ручке и бумаге. Есть ли другой способ найти все возможные комбинации чисел «n» (где хотя бы одно число соседствует с другим). Есть ли у нас формула для этого? куда я подключаю, и он сообщает мне, сколько существует возможных фигур?