Назад к лучшим решениям 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. }