UVA 10827 Maximum sum on a torus(子矩阵之和变形）

Problem H
Maximum sum on a torus
Input: Standard Input

Output: Standard Output

A grid that wraps both horizontally and vertically is called a torus. Given a torus where each cell contains an integer, determine the sub-rectangle with the largest sum. The sum of a sub-rectangle is the sum of all the elements in that rectangle. The grid below shows a torus where the maximum sub-rectangle has been shaded.

1
-1
0
0
-4

2
3
-2
-3
2

4
1
-1
5
0

3
-2
1
-3
2

-3
2
4
1
-4

Input

The first line in the input contains the number of test cases (at most 18). Each case starts with an integer N (1≤N≤75) specifying the size of the torus (always square). Then follows N lines describing the torus, each line containing N integers between -100 and 100, inclusive.

Output
For each test case, output a line containing a single integer: the maximum sum of a sub-rectangle within the torus.

Sample Input Output for Sample Input
251 -1 0 0 -42 3 -2 -3 24 1 -1 5 03 -2 1 -3 2-3 2 4 1 -431 2 34 5 67 8 9 1545

题意：大概就是给定一个矩阵。求一个子矩阵之和最大。。。但是多了一点。就是这个矩阵是环形的。。就是比如n列和第1列也算是相连的。

思路:把矩阵扩大4倍。变成一个4倍的矩阵，就解决了环的问题。然后枚举的时候只要枚举小于n*n的矩阵。。具体方法和这题类似

代码：

#include 
#include 
#include 

int t, n, num[160][160], sum[160], he, Max;

void init() {
    scanf("%d", &n);
    Max = -INT_MAX;
    for (int i = 0; i < n; i ++)
	for (int j = 0; j < n; j ++) {
	    scanf("%d", &num[i][j]);
	    num[i][j + n] = num[i + n][j] = num[i + n][j + n] = num[i][j];
	    if (Max < num[i][j])
		Max = num[i][j];
	}
}

int solve() {
    for (int i = 0; i < n; i ++) {
	for (int j = 0; j < n; j ++) {
	    memset(sum, 0, sizeof(sum));
	    for (int k = i; k < n + i; k ++) {
		he = 0;
		for (int l = j; l < n + j; l ++) {
		    sum[l] += num[k][l];
		    he += sum[l];
		    if (Max < he)
			Max = he;
		}
	    }
	}
    }
    return Max;
}
int main() {
    scanf("%d", &t);
    while (t --) {
	init();
	printf("%d\n", solve());
    }
    return 0;
}