Назад к лучшим решениям Status: AC, problem ZDIP, contest ZEL07. By werewolf (Werewolf), 2007-02-27 02:45:11.
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5.  
  6. typedef unsigned char byte;
  7.  
  8. byte q, h, w, th;
  9. byte noised_image[200][200];
  10. byte median_image[200][200];
  11. byte grad_image[200][200];
  12. byte sub_image[200][200];
  13.  
  14. short levels[256];
  15.  
  16. #define abs(x) ((x)>0?(x):-(x))
  17. #define in(x, a, b) ((x)>=(a) && (x)<(b))
  18.  
  19. /*
  20. static const char dirs[][2][2] =
  21. {
  22. {{-1, -1}, {0, 1}}, {{0, -1}, {0, 1}}, {{1, -1}, {0, 1}}, {{-1, -2}, {0, 1}}, {{0, -2}, {0, 1}}, {{1, -2}, {0, 1}},
  23. {{0, -1}, {1, 1}}, {{-1, 0}, {1, 1}}, {{-1, -1}, {1, 1}}, {{-1, -2}, {1, 1}}, {{-2, -1}, {1, 1}}, {{-2, -2}, {1, 1}},
  24. {{0, -1}, {-1, 1}}, {{1, 0}, {-1, 1}}, {{1, -1}, {-1, 1}}, {{1, -2}, {-1, 1}}, {{2, -1}, {-1, 1}}, {{2, -2}, {-1, 1}},
  25. {{-1, 2}, {0, -1}}, {{0, 2}, {0, -1}}, {{1, 2}, {0, -1}},
  26. {{-1, 0}, {1, -1}}, {{-1, 2}, {1, -1}}, {{-2, 1}, {1, -1}}, {{-2, 2}, {1, -1}},
  27. {{1, 0}, {-1, -1}}, {{1, 2}, {-1, -1}}, {{2, 1}, {-1, -1}}, {{2, 2}, {-1, -1}},
  28.  
  29. {{1, 0}, {-1, 0}}, {{2, -1}, {-1, 0}}, {{2, 0}, {-1, 0}}, {{2, 1}, {-1, 0}},
  30. {{-2, -1}, {1, 0}}, {{-2, 0}, {1, 0}}, {{-2, 1}, {1, 0}}
  31. };
  32. */
  33.  
  34. static const char dirs[][2][2] =
  35. {
  36. {{-1, -1}, {0, 1}}, {{0, -1}, {0, 1}}, {{1, -1}, {0, 1}},
  37. {{0, -1}, {1, 1}}, {{-1, 0}, {1, 1}}, {{-1, -1}, {1, 1}},
  38. {{0, -1}, {-1, 1}}, {{1, 0}, {-1, 1}}, {{1, -1}, {-1, 1}},
  39.  
  40. {{-1, 0}, {1, -1}},
  41. {{1, 0}, {-1, -1}},
  42.  
  43. {{1, 0}, {-1, 0}},
  44. };
  45.  
  46. #define w_size 4
  47. static const char w_coords[w_size][2] =
  48. { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
  49.  
  50. /*
  51. #define w_size 8
  52. static const char w_coords[w_size][2] =
  53. { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
  54. */
  55. void init()
  56. {
  57. memset(levels, 0, sizeof(levels));
  58. }
  59. void readImage();
  60. void writeImage();
  61. #ifdef ONLINE_JUDGE
  62. void readImage()
  63. {
  64. int i, j;
  65. char str[800], *p;
  66. gets(str);
  67. sscanf(str, "%d%d%d", &q, &h, &w);
  68.  
  69. for(i = 0; i < h; i++)
  70. {
  71. gets(str);
  72. p = str;
  73. for(j = 0; j < w; j++)
  74. {
  75. noised_image[i][j] = atoi(p);
  76. p++;
  77. while( *p && *(p++) != ' ' );
  78. }
  79. }
  80. }
  81. void writeImage()
  82. {
  83. int i, j;
  84. printf("%d %d\n", h, w);
  85. for(i = 0; i < h; i++)
  86. {
  87. for(j = 0; j < w; j++)
  88. {
  89. printf("%03d ", noised_image[i][j]);
  90. }
  91. printf("\n");
  92. }
  93. }
  94. #endif
  95. int btcmp( const void *arg1, const void *arg2 )
  96. {
  97. return *(byte*)arg1<*(byte*)arg2?-1:*(byte*)arg1==*(byte*)arg2?0:1;
  98. }
  99. void simpleInterpolate()
  100. {
  101. int i, j, k;
  102. byte window[w_size+1];
  103. for(i = 0; i < h; i++)
  104. {
  105. for(j = 0; j < w; j++)
  106. {
  107. int l, m;
  108. for(k = 0; k < w_size; k++)
  109. {
  110. l = i + w_coords[k][0];
  111. m = j + w_coords[k][1];
  112. if(l < 0 || l >= h || m < 0 || m >= w)
  113. {
  114. window[k] = noised_image[i][j];
  115. }else
  116. window[k] = noised_image[l][m];
  117. }
  118. window[k] = noised_image[i][j];
  119.  
  120. qsort(window, w_size+1, sizeof(byte), btcmp);
  121.  
  122. median_image[i][j] = window[w_size/2];
  123. }
  124. }
  125. }
  126. void findOrthoGrad()
  127. {
  128. int i, j, k;
  129. for(i = 0; i < h; i++)
  130. {
  131. for(j = 0; j < w; j++)
  132. {
  133. byte diff = 255, val = noised_image[i][j];
  134. int x1, y1, x2, y2;
  135. for(k = 0; k < sizeof(dirs)/sizeof(dirs[0]); k++)
  136. {
  137. x1 = j + dirs[k][0][0];
  138. y1 = i + dirs[k][0][1];
  139. x2 = j + dirs[k][1][0];
  140. y2 = i + dirs[k][1][1];
  141.  
  142. if(!in(x1, 0, w) || !in(x2, 0, w) || !in(y1, 0, h) || !in(y2, 0, h))
  143. continue;
  144.  
  145. if(abs(noised_image[y1][x1] - noised_image[y2][x2]) < diff)
  146. {
  147. diff = abs(noised_image[y1][x1] - noised_image[y2][x2]);
  148. val = (noised_image[y1][x1] + noised_image[y2][x2])/2;
  149. }
  150. }
  151. grad_image[i][j] = val;
  152. }
  153. }
  154. }
  155. void subImage()
  156. {
  157. int i, j, k;
  158. for(i = 0; i < h; i++)
  159. {
  160. for(j = 0; j < w; j++)
  161. {
  162. sub_image[i][j] = abs(noised_image[i][j] - grad_image[i][j]);
  163. if(sub_image[i][j] != 0)
  164. levels[sub_image[i][j]]++;
  165. }
  166. }
  167. }
  168. void selectThreshhold()
  169. {
  170. byte i;
  171. int npoints = (h*w*q )/70, sum = 0, d = 255*h*w;
  172.  
  173. for(i=255; i>0; i--)
  174. {
  175. if(abs(levels[i]+sum-npoints) < d)
  176. {
  177. th = i;
  178. sum += levels[i];
  179. d = abs(sum-npoints);
  180. }
  181. }
  182. }
  183. void removeNoise()
  184. {
  185. int i, j;
  186. for(i = 0; i < h; i++)
  187. {
  188. for(j = 0; j < w; j++)
  189. {
  190. if(sub_image[i][j] >= th)
  191. noised_image[i][j] = median_image[i][j];
  192. }
  193. }
  194. }
  195.  
  196. int main()
  197. {
  198. int t;
  199. char str[5];
  200. gets(str);
  201. t = atoi(str);
  202.  
  203. while(t--)
  204. {
  205. init();
  206. readImage();
  207. simpleInterpolate();
  208. findOrthoGrad();
  209. subImage();
  210. selectThreshhold();
  211. removeNoise();
  212. writeImage();
  213.  
  214. }
  215. return 0;
  216. }