Назад к лучшим решениям Status: AC, problem ZDIP, contest ZEL07. By levlam (Levin Aleksey), 2007-03-04 00:15:32.
  1. #include <stdio.h>
  2. #define abs(x) ((x)<0?(-(x)):(x))
  3. int a[205][205], b[205][205], m, n, K=8;
  4. int dx[9]={  1, -1,  0,  0,  1,  1, -1, -1};
  5. int dy[9]={  0,  0, -1,  1,  1, -1,  1, -1};
  6. int w [9]={  100,  100,  100,  100,  1,  1,  1,  1};
  7.  
  8. void check(int i, 
int j, int p)
  9. {
  10.    int l, x, y, k=0, kk=0, s=0, min=255, max=0, t, id, d[9], nd[9], kd=0;
  11.    for (l=0; l<4; l++)
  12.    {
  13.       x=i+dx[l];
  14.       y=j+dy[l];
  15.       if (x>=0 && x<m && y>=0 && y<n)
  16.       {
  17.          t=b[x][y];
  18.          if (t!=-1)
  19.          {
  20.             s+=t;
  21.             if (t>max) max=t;
  22.             if 
(t<min) min=t;
  23.             k++;
  24.             for (id=0; id<kd && abs(d[id]/nd[id]-t)>=11; id++) ;
  25.             if (id==kd) d[kd]=t, nd[kd++]=1;
  26.             else d[id]+=t, nd[id]++;
  27.          }
  28.          kk++;
  29.       }
  30.    }
  31.    if (k>=kk-p)
  32.    {
  33.       if (k!=0)
  34.       {
  35.          for (id=0; id<kd && k-nd[id]>1; id++) ;
  36.          if (id<kd && k>2) b[i][
j]=(d[id]+d[id]+nd[id])/(nd[id]+nd[id]);
  37.          else b[i][j]=s/k;
  38.       }
  39.       else b[i][j]=128;
  40.    }
  41.    if (k>1 && max-min<=5) b[i][j]=(s+s+k)/(k+k);//(max+min)>>1;
  42.    if (b[i]
[j]!=-1)
  43.    for (l=0; l<4; l++)
  44.    {
  45.       x=i+dx[l];
  46.       y=j+dy[l];
  47.       if (x>=0 && x<m && y>=0 && y<n && b[x][y]==-1)
  48.          check(x,y,p);
  49.    }
  50. }
  51.  
  52. int main(void)
  53. {
  54.    int i, j, l, q, tn, nt, x, y, p, st, s, k, min, max, t, id, d[9], nd[9], kd, min1, max1, min2, max2;
  55.    #ifndef ONLINE_JUDGE
  56.    freopen("input.txt", "r", stdin);
  57.    freopen("output.txt", "w", stdout);
  58.    
#endif
  59.    scanf("%d", &nt);
  60.    for (tn=0; tn<nt; tn++)
  61.    {
  62.       scanf("%d%d%d", &q, &m ,&n);
  63.       for (i=0; i<m; i++)
  64.          for (j=0; j<n; j++)
  65.             scanf("%d", &a[i][j]);
  66.       for (st=0; st<5; st++)
  67.       {
  68.       for (i=0; i<m; i++)
  69.          for (j=0; j<n; j++
)
  70.          {
  71.             max=0, min=255, kd=0, p=255;
  72.             min1=255, max1=0, min2=255, max2=0;
  73.             for (k=s=l=0; l<4; l++)
  74.             {
  75.                x=i+dx[l];
  76.                y=j+dy[l];
  77.                if (x>=0 && x<m && y>=0 && y<n)
  78.                {
  79.                   t=a[x][y];
  80.                   if (abs(t-a[i][j])<p) p=abs(t-a[i]
[j]);
  81.                   s+=t*w[l];
  82.                   if (t>max && l<4) max=t;
  83.                   if (t<min && l<4) min=t;
  84.                   if (l<2)
  85.                   {
  86.                      if (t>max1 && l<4) max1=t;
  87.                      if (t<min1 && l<4) min1=t;
  88.                   }
  89.                   else
  90.                   {
  91.                      if (t>max2 && l<4) max2=t;
  92.                      if (t<min2 && l<4) min2=t;
  93.                   }
  94.                   k+=w[l];
  95.                   for (id=0; id<kd && abs
(d[id]/nd[id]-t)>=7; id++) ;
  96.                   if (id==kd) d[kd]=t, nd[kd++]=1;
  97.                   else d[id]+=t, nd[id]++;
  98.                }
  99.             }
  100.             if (p>7)
  101.             {
  102.                if (k>1 && max-min<=41) b[i][j]=(s+s+k)/(k+k);
  103.                else
  104.                {
  105.                   for (id=0; id<kd && k-nd[id]*w[
0]>w[0]; id++) ;
  106.                   if (id<kd && k>2*w[0]) b[i][j]=(d[id]+d[id]+nd[id])/(nd[id]+nd[id]);
  107.                   else
  108.                      if (abs((s+s+k)/(k+k)-a[i][j])<=65) b[i][j]=a[i][j];
  109.                      else b[i][j]=-1;
  110.                }
  111.             }
  112.             else
 b[i][j]=a[i][j];
  113.          }
  114.       for (i=0; i<m; i++)
  115.          for (j=0; j<n; j++)
  116.             if (b[i][j]==-1) check(i,j,0);
  117.       for (i=0; i<m; i++)
  118.          for (j=0; j<n; j++)
  119.             if (b[i][j]==-1) check(i,j,
1);
  120.       for (i=0; i<m; i++)
  121.          for (j=0; j<n; j++)
  122.             if (b[i][j]==-1) check(i,j,2);
  123.       for (i=0; i<m; i++)
  124.          for (j=0; j<n; j++)
  125.             if (b[i][j]==-1) check(i,j,5);
  126.       for (i=0; i<m; i++)
  127.          for (j=0; j<n; j++)
  128.             a[i][j]=b[i][j];            
  129.       }
  130.       
printf("%d %d\n", m, n);
  131.       for (i=0; i<m; i++)
  132.       {
  133.          for (j=0; j<n; j++)
  134.             printf(" %03d", b[i][j]);
  135.          printf("\n");
  136.       }
  137.    }
  138.    return 0;
  139. }