题目:在一个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
解答:
其实没啥好分析的,遍历每一个数,然后找这个数横向和纵向的N-1个数的和,找到最大值。
接着找每个数的右下和左下N-1个数的和,求取最大值。
唯一值得注意的就是不要越界。
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <math.h> 5 using namespace std; 6 int Max(int a, int b) { return a < b ? b : a; } 7 int N, D, a, answer; 8 int rowAndCol (const vector<vector<int>> &v, int ans) { 9 int sumR = 0, sumC = 0; 10 for (size_t i = 0; i < v.size() - D + 1; i++) 11 { 12 for (size_t j = 0; j < v[0].size() - D + 1; j++) 13 { 14 for (size_t k = 0; k < D; k++) 15 { 16 sumR += v[i][j + k]; 17 sumC += v[i + k][j]; 18 } 19 ans = Max(sumR, Max(sumC, ans)); 20 sumR = sumC = 0; 21 } 22 } 23 return ans; 24 } 25 int duiJiaoXian (const vector<vector<int>> &v, int ans) { 26 int sum1030 = 0, sum0130 = 0; 27 for (size_t i = 0; i < v.size() - D + 1; i++) 28 { 29 for (size_t j = 0; j < v.size() - D + 1; j++) 30 { 31 for (size_t k = 0; k < D; k++) 32 { 33 sum1030 += v[i + k][j + k]; 34 sum0130 += v[i + k][v.size() - j - k - 1]; 35 } 36 ans = Max(sum1030, Max(sum0130, ans)); 37 sum1030 = sum0130 = 0; 38 } 39 } 40 return ans; 41 } 42 int main() { 43 cin >> N >> D; 44 vector<int> vNei; 45 vector<vector<int>> vWai(N); 46 for (auto j = 0; j < N; j++) 47 { 48 for (auto i = 0; i < N; i++) 49 { 50 cin >> a; 51 vWai[j].push_back(a); 52 } 53 } 54 answer = rowAndCol(vWai,answer); 55 answer = duiJiaoXian(vWai, answer); 56 cout << answer; 57 }