题目
在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值
输入描述
每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D :
3 <= N <= 100
1 <= D <= N
接下来有N行，每行N个数字d:
0 <= d <= 100
输出描述
输出一个整数，表示找到的和的最大值
输入例子
4 2
87 98 79 61
10 27 95 70
20 64 73 29
71 65 15 0
输出例子
193
问题分析
每个点需要计算八个方向D个数的和，可以用暴力枚举计算，这样会有很多重复计算
对于每个点，我只计算，→，↓，↘，↗四个方向的值。
代码
#include <iostream>
using namespace std;
int getMax(int *array, int n, int d) {
int max_sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int line_heng = 0, line_shu = 0, you_shang_line = 0, you_xia_line = 0;
for (int k = 0; k < d; k++) {
if (i + d <= n) {
line_shu += array[(i + k) * n + j];
if(j + d <= n) {
you_xia_line += array[(i + k) * n + j + k];
}
}
if (j + d <= n) {
line_heng += array[i * n + j + k];
if (i >= d - 1) {
you_shang_line += array[(i - k) * n + j + k];
}
}
}
max_sum = max(max_sum, line_shu);
max_sum = max(max_sum, line_heng);
max_sum = max(max_sum, you_xia_line);
max_sum = max(max_sum, you_shang_line);
}
}
return max_sum;
}
int main() {
int n, d, a;
cin >> n >> d;
int *array = new int[n * n];
for (int i = 0; i < n * n; i++) {
cin >> a;
array[i] = a;
}
cout << getMax(array, n, d) << endl;
return 0;
}
