首页 > 代码库 > uva10827-Maximum sum on a torus(矩阵最大和的变形)

uva10827-Maximum sum on a torus(矩阵最大和的变形)

题目;uva10827-Maximum sum on a torus(矩阵最大和的变形)


题目大意:就是uva108的变形,矩阵能够连通,就是能够从后面连到前面。这里把矩阵复制三遍,然后又一次生成一个大的矩阵,就能够解决联通的问题。再枚举矩阵的起点和终点全部情况,保留最大值就能够了。

比如:1 2 3

       2 3 4

新的矩阵: 1 2 3  1 2 3

                   2 3 4  2 3 4

                   1 2 3   1 2 3

                   2 3 4   2 3 4


代码:

#include <stdio.h>
#include <string.h>

const int N = 200;
const int INF = 0x3f3f3f3f;
int mat[N][N], temx[N], temy[N];
int n;

int Max (const int x, const int y) {return x > y? x: y;}

int main () {

	int t;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%d", &n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {

				scanf ("%d", &mat[i][j]);
				mat[i][j + n] = mat[i + n][j] = mat[i + n][j + n] = mat[i][j];
			}
		
		int mm = -INF;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				memset (temx, 0, sizeof (temx));
				for (int x = i; x < i + n; x++) {	
					for (int y = j; y < j + n; y++) {
						
							if (y == j)
								temy[y] = mat[x][y];
							else
								temy[y] = temy[y - 1] + mat[x][y];
							temx[y] += temy[y];	
							mm = Max (mm, temy[y]);
							mm = Max (mm, temx[y]);
					}
			}
		}
	}
	printf ("%d\n", mm);
	}
	return 0;
}


uva10827-Maximum sum on a torus(矩阵最大和的变形)