Назад к лучшим решениям 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}}, 
  26.   {{-1, 2}, {0, -1}}, {{0, 2}, {0, -1}}, {{1, 2}, {0, -1}}, 
  27.   {{-1, 0}, {1, -1}}, {{-1, 2}, {1, -1}}, {{-2, 1}, {1, -1}}, {{-2, 2}, {1, -1}}, 
  28.   {{1, 0}, {-1, -1}}, {{1, 2}, {-1, -1}}, {{2, 1}, {-1, -1}}, {{2, 2}, {-1, -1}}, 
  29.  
  30.   {{1, 0}, {-1, 0}}, {{2, -1}, {-1, 0}}, {{2, 0}, {-1, 0}}, {{2, 1}, {-1, 0}}, 
  31.   {{-2, -1}, {1, 0}}, {{-2, 0}, {1, 0}}, {{-2, 1}, {1, 0}}
  32. };
  33. */
  34.  
  35. static const char dirs[][2][2] = 
  36. { 
  37.   {{-1, -1}, {0, 1}}, {{0, -1}, {0, 1}}, {{1, -1}, 
{0, 1}},
  38.   {{0, -1}, {1, 1}}, {{-1, 0}, {1, 1}}, {{-1, -1}, {1, 1}},
  39.   {{0, -1}, {-1, 1}}, {{1, 0}, {-1, 1}}, {{1, -1}, {-1, 1}}, 
  40.  
  41.   {{-1, 0}, {1, -1}},
  42.   {{1, 0}, {-1, -1}},
  43.  
  44.   {{1, 0}, {-1, 0}}, 
  45. };
  46.  
  47. #define w_size 4
  48. static const char w_coords[w_size][2] = 
  49. { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
  50.  
  51. /*
  52. #define w_size 8
  53. static const char w_coords[w_size][2] = 
  54. { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
  55. */
  56. void init()
  57. {
  58. 	memset(levels, 0, sizeof(levels));
  59. }
    60. 

  60. void readImage();
  61. void writeImage();
  62. #ifdef ONLINE_JUDGE
  63. void readImage()
  64. {
  65. 	
int i, j;
  66. 	char str[800], *p;
  67. 	gets(str);
  68. 	sscanf(str, "%d%d%d", &q, &h, &w);
  69.  
  70. 	for(i = 0; i < h; i++)
  71. 	{
  72. 		gets(str);
  73. 		p = str;
  74. 		for(j = 0; j < w; j++)
  75. 		{
  76. 			noised_image[i][j] = atoi(p);
  77. 			p++;
  78. 			while( *p && *(p++) != ' ' );				
  79. 		}
  80. 	}
  81. }
  82. void writeImage()
  83. {
  84. 	int i, j;
  85. 	printf("%d %d\n", h, w);
  86. 	for(i = 0; i < h; i++)
  87. 	{
  88. 		for(j = 0; j < w; j++)
  89. 		{
  90. 			printf("%03d ", noised_image[i][j]);			
  91. 		}
  92. 		printf("\n");
  93. 	}
  94. }
  95. #endif
  96. int btcmp( const void *arg1, const void *arg2 )
  97. {
  98. 	return *(byte*)arg1<*(byte*)arg2?-1:*(byte*)arg1==*(byte*)arg2?0:1;
  99. }
  100. void simpleInterpolate()
  101. {
  102. 	int i, j, k;
  103. 	byte window[w_size+1];
  104. 

    	for(i = 0; i < h; i++)
  105. 	{
  106. 		for(j = 0; j < w; j++)
  107. 		{
  108. 			int l, m;
  109. 			for(k = 0; k < w_size; k++)
  110. 			{
  111. 				l = i + w_coords[k][0];
  112. 				m = j + w_coords[k][1];
  113. 				if(l < 0 || l >= h || m < 0 || m >= w)
  114. 				{
  115. 					window[k] = noised_image[i][j];
  116. 				}else
  117. 					window[k] = noised_image[l][m];
  118. 			}
  119. 			window[k] = noised_image[i][j];
  120.  
  121. 			qsort(window, w_size+1, sizeof(byte), btcmp);
  122.  
  123. 			median_image[i][j] = window[w_size/2];
  124. 		}
  125. 	}
  126. }
  127. void findOrthoGrad()
  128. {
  129. 	int i, j, k;
  130. 	
  131. 	for(i = 0; i < h; i++)
  132. 	{
  133. 		for(j = 0; j < w; j++)
  134. 		{
  135. 			byte diff = 255, val = noised_image[i][j];
  136. 			int x1, y1, x2, y2;
  137. 			for(k = 0; k < sizeof(dirs)/sizeof(dirs[0]); k++)
  138. 			{
  139. 				x1 = j + dirs[k][0][0];
  140. 				y1 = i + dirs[k][0][1];
  141. 				
x2 = j + dirs[k][1][0];
  142. 				y2 = i + dirs[k][1][1];
  143.  
  144. 				if(!in(x1, 0, w) || !in(x2, 0, w) || !in(y1, 0, h) || !in(y2, 0, h))
  145. 					continue;
  146.  
  147. 				if(abs(noised_image[y1][x1] - noised_image[y2][x2]) < diff)
  148. 				{
  149. 					diff = abs(noised_image[y1][x1] - noised_image[y2][x2]);
  150. 					val = (noised_image[y1][x1] + noised_image[y2][x2])/2;
  151. 				}
  152. 				
  153. 			}
  154. 			grad_image[i][j] = val;
  155. 		}
  156. 	}
  157. }
  158. void subImage()
  159. {
  160. 	int i, j, k;
  161. 	for(i = 0; i < h; i++)
  162. 	{
  163. 		for(j = 0; j < w; j++)
  164. 		{
  165. 			sub_image[i][j] = abs(noised_image[i][j] - grad_image[i][j]);
  166. 			if(sub_image[i][j] != 0)
  167. 				levels[sub_image[i][j]]++;
  168. 		}
  169. 	}
  170. }
  171. void selectThreshhold()
  172. {
  173. 	byte i;
  174. 	int npoints = (h*w*q
)/70, sum = 0, d = 255*h*w;
  175.  
  176. 	for(i=255; i>0; i--)
  177. 	{
  178. 		if(abs(levels[i]+sum-npoints) < d)
  179. 		{
  180. 			th = i;
  181. 			sum += levels[i];
  182. 			d = abs(sum-npoints);
  183. 		}
  184. 	}
  185. }
  186. void removeNoise()
  187. {
  188. 	int i, j;
  189. 	for(i = 0; i < h; i++)
  190. 	{
  191. 		for(j = 0; j < w; j++)
  192. 		{
  193. 			if(sub_image[i][j] >= th)
  194. 				noised_image[i][j] = median_image[i][j];
  195. 		}
  196. 	}
  197. }
  198.  
  199. int main()
  200. {
  201. 	int t;
  202. 	char str[5];
  203. 	gets(str);
  204. 	t = atoi(str);
  205.  
  206. 	while(t--)
  207. 	{
  208. 		init();
  209. 		readImage();
  210. 		simpleInterpolate();
  211. 		findOrthoGrad();
  212. 		subImage();
  213. 		selectThreshhold();
  214. 		removeNoise();
  215. 		writeImage();
  216.  
  217. 	}
  218. 	return 0;
  219. }