Largest product in a grid

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

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

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

1.方向数组法

主要思路：

  1. 将数据录入数据数组
  2. 在某一点(i, j)使用for循环对4个方向进行遍历
  3. 在每个方向上使用for循环求连续数据乘积
  4. 尝试更新结果

image-20210411215047140

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
33
34
35
36
37
#include<iostream>
using namespace std;

int ans;
int num[30][30];
int dirx[4] = {-1, 0, 1, 1};//横坐标的方向数组
int diry[4] = {1, 1, 1, 0};//纵坐标的方向数组

int main(){
    //为了防止在利用方向数组判断时出现数组越界的情况，在数组坐标(5, 5)处开始读入
    for(int i = 5; i < 25; ++i){
        for(int j = 5; j < 25; ++j){
            cin >> num[i][j];
        }
    }

    for(int i = 5; i < 25; ++i){
        for(int j = 5; j < 25; ++j){
            //1.在(i, j)点处使用for循环遍历4个大方向
            for(int k = 0; k < 4; ++k){
                //定义临时变量t记录每个方向的答案
                int t = num[i][j];
                //2.在每个大方向处使用for循环求新坐标下的数值，最后求出数字乘积
                for(int l = 1; l <= 3; ++l){
                    int x = i + l * dirx[k];
                    int y = j + l * diry[k];
                    t *= num[x][y];
                }
                //3.尝试更新每个方向的答案
                ans = max(ans, t);
            }
            
        }
    }
    cout << ans << endl;
    return 0;
}