有没有会的？ -【ACM】【ZOJ1074】最大子矩阵和解决办法
有没有会的？？？ -----【ACM】【ZOJ1074】最大子矩阵和
Problem Description
给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。
Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y（0<m,n<1000 AND 0<x<=m AND 0<y<=n），表示给定的矩形有m行n列。接下来这个矩阵，有m行，每行有n个不大于1000的正整数。
Output
对于每组数据，输出一个整数，表示子矩阵的最大和。
Sample Input
14 5 2 23 361 649 676 588992 762 156 993 169662 34 638 89 543525 165 254 809 280
Sample Output
2474
求助，为什么我的代码会WA， 不想要标程哈， 哪位大牛帮忙讲解下行吗！！！！
我的代码(很暴力， 不过好像不会超时 就是WA)：
# include <stdio.h>
# include <string.h>
# define N 1000
int arr[N+1][N+1];
int sum[N+1][N+1];
int temp[N+1][N+1];
int main()
{
int t, i, j, x, y, m, n, max,mid;
scanf("%d", &t);
while (t--)
{
scanf("%d %d %d %d", &m, &n, &x, &y);
memset(sum, 0, sizeof(sum));
for (i=1; i<=m; ++i)
{
for (j=1; j<=n; ++j)
{
scanf("%d", &arr[i][j]);
sum[i][j] = sum[i-1][j] + arr[i][j];
}
}
for (i=x; i<=m; ++i)
{
for (j=1; j<=n; ++j)
{
temp[i][j] = sum[i][j] - sum[i-x][j]; //temp存竖下来的值
}
}
for (i=x; i<=m; ++i)
{
for (j=y; j<=n; ++j)
{
mid = 0;
for (int k=0; k<y; ++k)
{
mid += temp[i][j-k];
}
printf("%d ", mid);
if (mid > max)
max = mid;
}
printf("\n");
}
printf("%d\n", max);
}
return 0;
}
------解决方案--------------------
int CreateArray2D(int ** &A,int N,int M)
{
ret = -1;
if(!A){
A = new int *[N];
for(int i=0;i<N;++i)
A[i] = new int[M];
ret = 0;
}
return ret;
}
int InputArray2D(int **A,int N,int M)
{
int ret = -1;
if(A){
for(int i=0;i<N;++i){
for(int j=0;j<M;++j){
cout << "A["<<i+1<<"]["<<j+1<<"]:";
cin >> A[i][j];}
cout << "--------------"<<i+1<<"-----------"<<endl;}
ret = 0;
}
return ret;
}
void FreeArray2D(int ** &A,int N,int M)
{
if(A){
for(int i=0;i<N;++i)
if(A[i]){delete []A[i];A[i]=0;}
delete []A;
A = 0;}
}
int main()
{
ret = -1;
int n,m,x,y,**a=0,max,t,xi=-1,yi=-1;
cout << "矩阵 行 列:";
cin >> n >> m;
cout << "子矩阵 行 列：";
cin >> x >> y;
if (n<=0||m<=0||x<=0||x>n||y<=0||y>m)
return ret;
if(CreateArray2D(a,n,m))return ret;
if(InputArray2D(a,n,m))return ret;
max = 0xffffffff;
for(int i=0,ilimit=n-x;i<ilimit;++i)
for(int j=0;jlimit=m-y;j<jlimit;++j)
if((t=MaxArray2D(a,n,m,x,y,i,j))>max){
max = t;
xi = i; yi =j;}
if(xi>=0 && yi>=0){
for(int i=xi,ii=0;ii<x;++i,++ii){
for(int j=yi,jj=0;jj<y;++j,++jj)
cout << a[i][j] << " ";
cout << endl;}
cout << "最大元素和是："<< max <<endl;}
FreeArray2D(a,n,m);
ret = 0;
return ret;
}
------解决方案--------------------
编程不仅仅是满足个人喜好，可复用与验证代码可以避免很多重复的劳动。
代码本身没有问题，只是不便查错而已，太多的不必要中间存储容易干扰阅读与故障排查。小而简单的代码要比大而全的代码灵活方便得多。
Problem Description
给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。
Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y（0<m,n<1000 AND 0<x<=m AND 0<y<=n），表示给定的矩形有m行n列。接下来这个矩阵，有m行，每行有n个不大于1000的正整数。
Output
对于每组数据，输出一个整数，表示子矩阵的最大和。
Sample Input
14 5 2 23 361 649 676 588992 762 156 993 169662 34 638 89 543525 165 254 809 280
Sample Output
2474
求助，为什么我的代码会WA， 不想要标程哈， 哪位大牛帮忙讲解下行吗！！！！
我的代码(很暴力， 不过好像不会超时 就是WA)：
# include <stdio.h>
# include <string.h>
# define N 1000
int arr[N+1][N+1];
int sum[N+1][N+1];
int temp[N+1][N+1];
int main()
{
int t, i, j, x, y, m, n, max,mid;
scanf("%d", &t);
while (t--)
{
scanf("%d %d %d %d", &m, &n, &x, &y);
memset(sum, 0, sizeof(sum));
for (i=1; i<=m; ++i)
{
for (j=1; j<=n; ++j)
{
scanf("%d", &arr[i][j]);
sum[i][j] = sum[i-1][j] + arr[i][j];
}
}
for (i=x; i<=m; ++i)
{
for (j=1; j<=n; ++j)
{
temp[i][j] = sum[i][j] - sum[i-x][j]; //temp存竖下来的值
}
}
for (i=x; i<=m; ++i)
{
for (j=y; j<=n; ++j)
{
mid = 0;
for (int k=0; k<y; ++k)
{
mid += temp[i][j-k];
}
printf("%d ", mid);
if (mid > max)
max = mid;
}
printf("\n");
}
printf("%d\n", max);
}
return 0;
}
------解决方案--------------------
int CreateArray2D(int ** &A,int N,int M)
{
ret = -1;
if(!A){
A = new int *[N];
for(int i=0;i<N;++i)
A[i] = new int[M];
ret = 0;
}
return ret;
}
int InputArray2D(int **A,int N,int M)
{
int ret = -1;
if(A){
for(int i=0;i<N;++i){
for(int j=0;j<M;++j){
cout << "A["<<i+1<<"]["<<j+1<<"]:";
cin >> A[i][j];}
cout << "--------------"<<i+1<<"-----------"<<endl;}
ret = 0;
}
return ret;
}
void FreeArray2D(int ** &A,int N,int M)
{
if(A){
for(int i=0;i<N;++i)
if(A[i]){delete []A[i];A[i]=0;}
delete []A;
A = 0;}
}
int main()
{
ret = -1;
int n,m,x,y,**a=0,max,t,xi=-1,yi=-1;
cout << "矩阵 行 列:";
cin >> n >> m;
cout << "子矩阵 行 列：";
cin >> x >> y;
if (n<=0||m<=0||x<=0||x>n||y<=0||y>m)
return ret;
if(CreateArray2D(a,n,m))return ret;
if(InputArray2D(a,n,m))return ret;
max = 0xffffffff;
for(int i=0,ilimit=n-x;i<ilimit;++i)
for(int j=0;jlimit=m-y;j<jlimit;++j)
if((t=MaxArray2D(a,n,m,x,y,i,j))>max){
max = t;
xi = i; yi =j;}
if(xi>=0 && yi>=0){
for(int i=xi,ii=0;ii<x;++i,++ii){
for(int j=yi,jj=0;jj<y;++j,++jj)
cout << a[i][j] << " ";
cout << endl;}
cout << "最大元素和是："<< max <<endl;}
FreeArray2D(a,n,m);
ret = 0;
return ret;
}
------解决方案--------------------
编程不仅仅是满足个人喜好，可复用与验证代码可以避免很多重复的劳动。
代码本身没有问题，只是不便查错而已，太多的不必要中间存储容易干扰阅读与故障排查。小而简单的代码要比大而全的代码灵活方便得多。