106 lines
3.3 KiB
C
106 lines
3.3 KiB
C
// 问题描述】
|
||
// 小蓝有一个 n 行 m 列的矩阵 a[i][j] ，他想在矩阵中找出一个“口”字形状的区域，使得区域上的值的和最大。
|
||
|
||
// 具体讲，一个“口”字形状的区域可以由两个坐标 (x1, y1) 和 (x2, y2) 确定，满足：
|
||
|
||
// 1 <= x1 < x2 <= n ；
|
||
// 1 <= y1 < y2 <= m ；
|
||
// x2 - x1 = y2 - y1 。
|
||
// 对应的区域由满足以下条件之一的点 (x, y) 构成：
|
||
|
||
// x1 <= x <= x2，且 y = y1 ，对应“口”的左边一竖；
|
||
// y1 <= y <= y2，且 x = x1 ，对应“口”的上面一横；
|
||
// x1 <= x <= x2，且 y = y2 ，对应“口”的右边一竖；
|
||
// y1 <= y <= y2，且 x = x2 ，对应“口”的下面一横。
|
||
// 请注意有些点满足以上条件的多个，例如左上角的点 (x1, y1) ，在计算时算为一个点。
|
||
|
||
// 区域上的值是指对应区域的所有点的值，即“口”字的框上的值，不含框内和框外的值。
|
||
|
||
// 【输入格式】
|
||
// 输入的第一行包含两个整数 n, m ，分别表示行数和列数。
|
||
|
||
// 接下来 n 行，每行包含 m 个整数，相邻数之间使用一个空格分隔，依次表示矩阵的每行每列的值，本部分的第 i 行第 j 列表示 a[i][j] 。
|
||
|
||
// 【输出格式】
|
||
// 输出一行包含一个整数，表示最大的和。
|
||
|
||
// 【样例输入】
|
||
// 5 6
|
||
// 1 -1 2 -2 3 -3
|
||
// -1 2 -2 3 -3 4
|
||
// 2 -2 3 -3 4 -4
|
||
// -2 3 -3 4 -4 5
|
||
// 3 -3 4 -4 5 -5
|
||
// 【样例输出】
|
||
// 4
|
||
// 【样例说明】
|
||
// 取 (x1, y1) = (1, 1) ， (x2, y2) = (5, 5) 可得到最大值。
|
||
|
||
// 【评测用例规模与约定】
|
||
// 对于 30% 的评测用例，1 <= n, m <= 30 ，-1000 <= a[i][j] <= 1000 。
|
||
|
||
// 对于 60% 的评测用例，1 <= n, m <= 100 ，-1000 <= a[i][j] <= 1000 。
|
||
|
||
// 对于所有评测用例，1 <= n, m <= 300 ，-1000 <= a[i][j] <= 1000 。
|
||
|
||
#include <stdio.h>
|
||
|
||
#define MAX 301
|
||
|
||
int a[MAX][MAX];
|
||
int row_sum[MAX][MAX];
|
||
int col_sum[MAX][MAX];
|
||
|
||
int main() {
|
||
int n, m;
|
||
scanf("%d %d", &n, &m);
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = 1; j <= m; j++) {
|
||
scanf("%d", &a[i][j]);
|
||
}
|
||
}
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
row_sum[i][0] = 0;
|
||
for (int j = 1; j <= m; j++) {
|
||
row_sum[i][j] = row_sum[i][j - 1] + a[i][j];
|
||
}
|
||
}
|
||
|
||
for (int j = 1; j <= m; j++) {
|
||
col_sum[j][0] = 0;
|
||
for (int i = 1; i <= n; i++) {
|
||
col_sum[j][i] = col_sum[j][i - 1] + a[i][j];
|
||
}
|
||
}
|
||
|
||
int max_sum = -1000000000;
|
||
|
||
int k_max = (n - 1 < m - 1) ? (n - 1) : (m - 1);
|
||
|
||
for (int k = 1; k <= k_max; k++) {
|
||
for (int x1 = 1; x1 <= n - k; x1++) {
|
||
int x2 = x1 + k;
|
||
for (int y1 = 1; y1 <= m - k; y1++) {
|
||
int y2 = y1 + k;
|
||
|
||
int sum_left = col_sum[y1][x2] - col_sum[y1][x1 - 1];
|
||
int sum_top = row_sum[x1][y2] - row_sum[x1][y1 - 1];
|
||
int sum_right = col_sum[y2][x2] - col_sum[y2][x1 - 1];
|
||
int sum_bottom = row_sum[x2][y2] - row_sum[x2][y1 - 1];
|
||
|
||
int sum_corners = a[x1][y1] + a[x1][y2] + a[x2][y1] + a[x2][y2];
|
||
|
||
int total = sum_left + sum_top + sum_right + sum_bottom - sum_corners;
|
||
|
||
if (total > max_sum) {
|
||
max_sum = total;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
printf("%d\n", max_sum);
|
||
return 0;
|
||
} |