#include<stdio.h> 
#include<string.h> 
#define MaxN 201 

int m,n,r,c; 
double mar[MaxN][MaxN]; 
double map[MaxN]; 
int x1,y1,x2,y2; 
int xx1,yy1,xx2,yy2; 
double tmp,max; 

int init() 
{ int i,j; 
 memset(mar,0,sizeof(mar)); 
 scanf("%d",&m); if (m==0) return 0; 
 scanf("%d %d %d",&n,&r,&c); 
 for (i=1; i<=m; i++) 
  for (j=1; j<=n; j++) 
   {scanf("%lf",&mar[i][j]); mar[i][j]+=mar[i-1][j];} 
 return 1; 
} 

void save() 
{max=tmp/(y2-y1+1); 
 xx1=x1; yy1=y1; xx2=x2; yy2=y2; 
} 

void check() 
{if (tmp/(y2-y1+1)>max) 
  save(); 
 else if (tmp/(y2-y1+1)==max) 
  {if (x1<xx1) 
    save(); 
   else if (x1==xx1&&y1<yy1) 
    save(); 
   else if (x1==xx1&&y1==yy1&&x2<xx2) 
    save(); 
   else if (x1==xx1&&y1==yy1&&x2==xx2&&y2<yy2) 
    save(); 
  } 
} 

void minmap() 
{ int i; 
 for (map[0]=0,i=1; i<=n; i++) map[i]=map[i-1]+map[i]; 
 tmp=map[c]; y1=1; y2=c; check(); 
 for (i=c+1; i<=n; i++) 
  {if ((tmp+map[i]-map[i-1])/(y2-y1+1+1)>=(map[i]-map[i-c])/c) 
    {tmp=tmp+map[i]-map[i-1]; y2++;} 
   else 
    {tmp=(map[i]-map[i-c]); y2++; y1=y2-c+1;} 
   check(); 
  } 
} 

void search() 
{ int i; 
 max=-1; xx1=-1; yy1=-1; xx2=-1; yy2=-1; 
 for (x1=1; x1<=m; x1++) 
  for (x2=x1+r-1; x2<=m; x2++) 
   {for (i=1; i<=n; i++) map[i]=(mar[x2][i]-mar[x1-1][i])/(x2-x1+1); 
    minmap(); 
   } 
 printf("%d %d %d %d\n",xx1,yy1,xx2,yy2); 
} 

int main() 
{while (init()) 
  search(); 
 printf("*\n"); 
 return 0; 
}

• 我随机了100组数据，你的程序有5组跟我的答案不同 (1633) dynamic 2003-11-04 18:22:28
  • 我的答案比你的优，而且相差1以上，应该不是精度问题，你的算法估计是有问题的 (0) dynamic 2003-11-04 18:27:25
    • 不过你的算法也是很接近最优解的，而且100组只相差了5组。官方数据好像只有3组，太弱了 (0) dynamic 2003-11-04 18:32:05
  • 把你随机出来的数据发给我吧,我加上去 (18) hawk 2003-11-04 18:48:02
    • done,数据虽然有100组，但宽都是1，也就是说不是卡速度的，如果想卡速度的话要随机一些大数据:) (22) dynamic 2003-11-04 18:58:15