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 <stdio.h>
#include <string.h>
#include <limits.h>

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;
}