Назад к лучшим решениям Status: AC, problem ZDIP, contest ZEL07. By ding0 (NETALL), 2007-03-15 21:20:41.
  1. #pragma warning(disable : 4996)
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <math.h>
  6.  
  7. #define maxSize 200
  8. #define byte unsigned char
  9.  
  10. int GetColorForResult(int row, int col);
  11. int GetColorForDiffValue(int row, int col);
  12.  
  13. bool badPoints[maxSize][maxSize];
  14.  
  15. void ClearBadPoints()
  16. {
  17. for (int i=0; i<maxSize; i++)
  18. for (int j=0; j<maxSize; j++)
  19. {
  20. badPoints[i][j] = false;
  21. }
  22. }
  23.  
  24. byte sourceImage[maxSize][maxSize];
  25. byte resultImage[maxSize][maxSize];
  26.  
  27. int q, h, w;
  28.  
  29. void ReadImage()
  30. {
  31. for (int i=0; i<h; i++)
  32. {
  33. for (int j=0; j<w; j++)
  34. {
  35. scanf("%d", &sourceImage[i][j]);
  36. }
  37. }
  38. }
  39.  
  40. void WriteImage()
  41. {
  42. printf("%d %d\n", h, w);
  43.  
  44. for (int i=0; i<h; i++)
  45. {
  46. if (i > 0) printf("\n");
  47.  
  48. for (int j=0; j<w; j++)
  49. {
  50. if (j > 0) printf(" ");
  51.  
  52. printf("%d", resultImage[i][j]);
  53. }
  54. }
  55. }
  56.  
  57.  
  58. long diffcount;
  59.  
  60. struct Diff
  61. {
  62. int i, j, value;
  63. };
  64.  
  65. Diff diffs[maxSize*maxSize];
  66.  
  67. void CopySourceToResult()
  68. {
  69. for (int i=0; i<h; i++)
  70. {
  71. for (int j=0; j<w; j++)
  72. {
  73. resultImage[i][j] = sourceImage[i][j];
  74. }
  75. }
  76. }
  77.  
  78. void CopyResultToSource()
  79. {
  80. for (int i=0; i<h; i++)
  81. {
  82. for (int j=0; j<w; j++)
  83. {
  84. sourceImage[i][j] = resultImage[i][j];
  85. }
  86. }
  87. }
  88.  
  89.  
  90. void QuickSort(long k1, long k2)
  91. {
  92. long in1, in2;
  93. int Temp;
  94. Diff v;
  95.  
  96. if ((k2-k1) > 1)
  97. {
  98. in1 = k1;
  99. in2 = k2;
  100. Temp = diffs[(k1+k2) / 2].value;
  101.  
  102. do
  103. {
  104. while (diffs[in1].value > Temp) in1++;
  105. while (diffs[in2].value < Temp) in2--;
  106.  
  107. if (in1 <= in2)
  108. {
  109. v = diffs[in1];
  110. diffs[in1] = diffs[in2];
  111. diffs[in2] = v;
  112. in1++;
  113. in2--;
  114. }
  115. } while (in1 <= in2);
  116.  
  117. if (k1 < in2) QuickSort(k1, in2);
  118. if (in1 < k2) QuickSort(in1, k2);
  119. }
  120. else
  121. {
  122. if (diffs[k1].value < diffs[k2].value)
  123. {
  124. v = diffs[k1];
  125. diffs[k1] = diffs[k2];
  126. diffs[k2] = v;
  127. }
  128. }
  129. }
  130.  
  131. void SortDiffs()
  132. {
  133. QuickSort(0, diffcount-1);
  134. }
  135.  
  136.  
  137. void ApplyDiffs()
  138. {
  139. long actualCount = h * w * q / 100;
  140.  
  141. if ((diffcount > 0) && (actualCount > 0))
  142. {
  143. for (int i=0; i<diffcount; i++)
  144. {
  145. diffs[i].value = abs(GetColorForDiffValue(diffs[i].i, diffs[i].j) - sourceImage[diffs[i].i][diffs[i].j]);
  146. }
  147.  
  148. SortDiffs();
  149.  
  150. if (diffcount < actualCount)
  151. {
  152. actualCount = diffcount;
  153. }
  154.  
  155. for (int i=0; i<actualCount; i++)
  156. {
  157. resultImage[diffs[i].i][diffs[i].j] = GetColorForResult(diffs[i].i, diffs[i].j);
  158. }
  159. }
  160. }
  161.  
  162. int GetCountBigger(int row, int col, int thres)
  163. {
  164. int res = 0;
  165.  
  166. for (int i=-1; i<=+1; i++)
  167. for (int j=-1; j<=+1; j++)
  168. if ((i != 0) || (j != 0))
  169. {
  170. if (((i + row) >= 0) && ((i + row) < h) && ((j + col) >= 0) && ((j + col) < w))
  171. {
  172. if (((int)sourceImage[i+row][j+col] - (int)sourceImage[row][col]) >= thres)
  173. {
  174. res++;
  175. }
  176. }
  177. }
  178.  
  179. return res;
  180. }
  181.  
  182. int GetCountSmaller(int row, int col, int thres)
  183. {
  184. int res = 0;
  185.  
  186. for (int i=-1; i<=+1; i++)
  187. for (int j=-1; j<=+1; j++)
  188. if ((i != 0) || (j != 0))
  189. {
  190. if (((i + row) >= 0) && ((i + row) < h) && ((j + col) >= 0) && ((j + col) < w))
  191. {
  192. if (((int)sourceImage[row][col] - (int)sourceImage[i+row][j+col]) >= thres)
  193. {
  194. res++;
  195. }
  196. }
  197. }
  198.  
  199. return res;
  200. }
  201.  
  202. int MeanAroundColor(int row, int col, bool useBadPoints)
  203. {
  204. int pointscount = 0;
  205. int res = 0;
  206.  
  207. for (int i=-1; i<=+1; i++)
  208. for (int j=-1; j<=+1; j++)
  209. if ((i != 0) || (j != 0))
  210. if (((i + row) >= 0) && ((i + row) < h) && ((j + col) >= 0) && ((j + col) < w))
  211. {
  212. if ((useBadPoints) || (!badPoints[i+row][j+col]))
  213. {
  214. res = res + sourceImage[i+row][j+col];
  215. pointscount++;
  216.  
  217. if ((i == 0) || (j == 0))
  218. {
  219. res = res + sourceImage[i+row][j+col];
  220. pointscount++;
  221. }
  222. }
  223. }
  224.  
  225. if (pointscount > 0)
  226. {
  227. res = res / pointscount;
  228. }
  229.  
  230. return res;
  231. }
  232.  
  233. int MedianColor(int row, int col, bool useBadPoints)
  234. {
  235. int pointscount = 0;
  236. int points[20];
  237.  
  238. for (int i=-1; i<=+1; i++)
  239. for (int j=-1; j<=+1; j++)
  240. //if ((i != 0) || (j != 0))
  241. if (((i + row) >= 0) && ((i + row) < h) && ((j + col) >= 0) && ((j + col) < w))
  242. {
  243. if ((useBadPoints) || (!badPoints[i+row][j+col]))
  244. {
  245. pointscount++;
  246. points[ pointscount] = sourceImage[i+row][j+col];
  247.  
  248. if (i*j == 0)
  249. {
  250. pointscount++;
  251. points[pointscount] = sourceImage[i+row][j+col];
  252.  
  253. if (i+j == 0)
  254. {
  255. pointscount++;
  256. points[pointscount] = sourceImage[i+row][j+col];
  257. pointscount++;
  258. points[pointscount] = sourceImage[i+row][j+col];
  259. }
  260. }
  261. }
  262. }
  263.  
  264. if (pointscount > 0)
  265. {
  266. for (int i=pointscount-1; i>=0; i--)
  267. for (int j=1; j<=i; j++)
  268. if (points[j] > points[j+1])
  269. {
  270. int temp = points[j];
  271. points[j] = points[j+1];
  272. points[j+1] = temp;
  273. }
  274. }
  275.  
  276. if ((pointscount % 2) != 0)
  277. {
  278. pointscount = (pointscount / 2) + 1;
  279. }
  280. else
  281. {
  282. pointscount = pointscount / 2;
  283. }
  284.  
  285. return points[pointscount];
  286. }
  287.  
  288. int GetAroundPointsCount(int row, int col)
  289. {
  290. int pointscount = 0;
  291. for (int i=-1; i<=+1; i++)
  292. for (int j=-1; j<=+1; j++)
  293. if ((i != 0) || (j != 0))
  294. if (((i + row) >= 0) && ((i + row) < h) && ((j + col) >= 0) && ((j + col) < w))
  295. {
  296. pointscount++;
  297. }
  298.  
  299. return pointscount;
  300. }
  301.  
  302.  
  303. void FilterSinglePoints(int thres)
  304. {
  305. for (int i=0; i<h; i++)
  306. for (int j=0; j<w; j++)
  307. {
  308. int pointsCount = GetAroundPointsCount(i, j);
  309.  
  310. int countB = GetCountBigger(i, j, thres);
  311. int countS = GetCountSmaller(i, j, thres);
  312.  
  313. if ((countB == pointsCount) || (countS == pointsCount))
  314. {
  315. diffcount++;
  316. diffs[diffcount].i = i;
  317. diffs[diffcount].j = j;
  318. badPoints[i][j] = true;
  319. }
  320. }
  321. }
  322.  
  323. int GetColorForDiffValue(int row, int col)
  324. {
  325. return MeanAroundColor(row, col, false);
  326. }
  327.  
  328. int GetColorForResult( int row, int col)
  329. {
  330. return MedianColor(row, col, false);
  331. }
  332.  
  333. void FillLines(bool testBlocked)
  334. {
  335. for (int i=0; i<h; i++)
  336. for (int j=0; j<w; j++)
  337. {
  338. // hor ->>>
  339. if (j + 4 < w)
  340. {
  341. if ((resultImage[i][j] == resultImage[i][j+1]) &&
  342. (resultImage[i][j] != resultImage[i][j+2]) &&
  343. (resultImage[i][j] == resultImage[i][j+3]) &&
  344. (resultImage[i][j] == resultImage[i][j+4]))
  345. {
  346. bool blocked = false;
  347.  
  348. if (testBlocked)
  349. {
  350. if ((i + 1 < h) &&
  351. (resultImage[i+1][j+2] == resultImage[i][j+2]))
  352. {
  353. blocked = true;
  354. }
  355.  
  356. if ((i - 1 > 0) &&
  357. (resultImage[i-1][j+2] == resultImage[i][j+2]))
  358. {
  359. blocked = true;
  360. }
  361. }
  362.  
  363. if (!blocked)
  364. {
  365. resultImage[i][j+2] = resultImage[i][j];
  366. }
  367. }
  368. }
  369.  
  370. // ver |
  371. // \|/
  372. if (i + 4 < h)
  373. {
  374. if ((resultImage[i][j] == resultImage[i+1][j]) &&
  375. (resultImage[i][j] != resultImage[i+2][j]) &&
  376. (resultImage[i][j] == resultImage[ i+3][j]) &&
  377. (resultImage[i][j] == resultImage[i+4][j]))
  378. {
  379. bool blocked = false;
  380.  
  381. if (testBlocked)
  382. {
  383. if ((j + 1 < w) &&
  384. (resultImage[i+2][j+1] == resultImage[i+2][j]))
  385. {
  386. blocked = true;
  387. }
  388.  
  389. if ((i - 1 > 0) &&
  390. (resultImage[i+2][j-1] == resultImage[i+2][j]))
  391. {
  392. blocked = true;
  393. }
  394. }
  395.  
  396. if (!blocked)
  397. {
  398. resultImage[i+2][j] = resultImage[i][j];
  399. }
  400. }
  401. }
  402. }
  403. }
  404.  
  405. bool SameColorAround(int row, int col, int sourcecolor, int thres)
  406. {
  407. bool res = false;
  408.  
  409. for (int i=-1; i<=+1; i++)
  410. {
  411. for (int j=-1; j<=+1; j++)
  412. if ((i != 0) || (j != 0))
  413. if (((i + row) >= 0) && ((i + row) < h) && ((j + col) >= 0) && ((j + col) < w))
  414. {
  415. if (abs(sourceImage[row][col] - sourceImage[row+i][col+j]) <= thres)
  416. {
  417. res = true;
  418. break;
  419. }
  420. }
  421.  
  422. if (res) break;
  423. }
  424. return res;
  425. }
  426.  
  427. void Filter(int thres, int sameThres)
  428. {
  429. for (int i=0; i<h; i++)
  430. for (int j=0; j<w; j++)
  431. {
  432. int sourcecolor = sourceImage[i][j];
  433. int aroundcolor = GetColorForDiffValue(i, j);
  434.  
  435. if ((abs(sourcecolor - aroundcolor) > thres) &&
  436. (!SameColorAround(i, j, sourcecolor, sameThres)))
  437. {
  438. diffcount++;
  439.  
  440. diffs[diffcount].i = i;
  441. diffs[diffcount].j = j;
  442. diffs[diffcount].value = abs(sourcecolor - aroundcolor);
  443.  
  444. badPoints[i][j] = true;
  445. }
  446. }
  447. }
  448.  
  449. void FilterAvatar(int thres)
  450. {
  451. int moda[256];
  452.  
  453. for (int i=0; i<h; i++)
  454. {
  455. moda[resultImage[i][0]]++;
  456. moda[resultImage[i][w-1]]++;
  457. }
  458.  
  459. for (int j=0; j<w; j++)
  460. {
  461. moda[resultImage[0][j]]++;
  462. moda[resultImage[h-1][j]]++;
  463. }
  464.  
  465. int best=0, bestcount=0;
  466.  
  467. for (int i=0; i<256; i++)
  468. {
  469. if (moda[i] > bestcount)
  470. {
  471. bestcount = moda[i];
  472. best = i;
  473. }
  474. }
  475.  
  476. if (bestcount > 350)
  477. {
  478. for (int i=0; i<h; i++)
  479. {
  480. if (abs(resultImage[i][0] - best) >= thres)
  481. {
  482. resultImage[i][0] = best;
  483. }
  484.  
  485. if (abs(resultImage[i][w-1] - best) >= thres)
  486. {
  487. resultImage[i][w-1] = best;
  488. }
  489. }
  490.  
  491. for (int j=0; j<w; j++)
  492. {
  493. if (abs(resultImage[0][j] - best) >= thres)
  494. {
  495. resultImage[0][j] = best;
  496. }
  497.  
  498. if (abs(resultImage[h-1][j] - best) >= thres)
  499. {
  500. resultImage[h-1][j] = best;
  501. }
  502. }
  503. }
  504. }
  505.  
  506. void Filter2x2Diagonal(int centerThres, int aroundThres, bool centerLighter)
  507. {
  508. int a = 1, b = -1;
  509.  
  510. if (!centerLighter)
  511. {
  512. a = -a;
  513. b = -b;
  514. }
  515.  
  516. int matrToUp [4][4] = { {0, 1, 1, 1}, {1, 1, 0, 1}, {1, 0, 1, 1}, {1, 1, 1, 0}};
  517. int matrToDown [4][4] = { {1, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 1}};
  518.  
  519. for (int i=-1; i<=h-3; i++)
  520. for (int j=-1; j<=w-3; j++)
  521. {
  522. // To up
  523. //
  524. if (abs((int)resultImage[i+2][j+1] - (int)resultImage[i+1][j+2]) <= centerThres)
  525. {
  526. int center = ((int)resultImage[i+2][j+1] + (int)resultImage[i+1][j+2]) / 2;
  527.  
  528. bool apply = true;
  529.  
  530. for (int ii=0; ii<4; ii++)
  531. {
  532. for (int jj=0; jj<4; jj++)
  533. if (((ii + i) >= 0) && ((ii + i) < h) && ((jj + j) >= 0) && ((jj + j) < w))
  534. if ((matrToUp[ii][jj] == 1) &&
  535. ((a*center + (int)b*resultImage[i+ii][j+jj]) < aroundThres))
  536. {
  537. apply = false;
  538. break;
  539. }
  540.  
  541. if (!apply) break;
  542. }
  543.  
  544. if (apply)
  545. {
  546. badPoints[i+2][j+1] = true;
  547. badPoints[i+1][j+2] = true;
  548.  
  549. resultImage[i+2][j+1] = MedianColor(i+2, j+1, false);
  550. resultImage[i+1][j+2] = MedianColor(i+ 1, j+2, false);
  551.  
  552. badPoints[i+2][j+1] = false;
  553. badPoints[i+1][j+2] = false;
  554. }
  555. }
  556.  
  557. // To down
  558. //
  559. if (abs((int)resultImage[i+1][j+1] - (int)resultImage[i+2][j+2]) <= centerThres)
  560. {
  561. int center = ((int)resultImage[i+1][j+1] + (int)resultImage[i+2][j+2]) / 2;
  562.  
  563. bool apply = true;
  564.  
  565. for (int ii=0; ii<4; ii++)
  566. {
  567. for (int jj=0; jj<4; jj++)
  568. if (((ii + i) >= 0) && ((ii + i) < h) && ((jj + j) >= 0) && ((jj + j) < w))
  569. if (( matrToDown[ii][jj] == 1) &&
  570. ((a*center + (int)b*resultImage[i+ii][j+jj]) < aroundThres))
  571. {
  572. apply = false;
  573. break;
  574. }
  575.  
  576. if (!apply) break;
  577. }
  578.  
  579. if (apply)
  580. {
  581. badPoints[i+1][j+1] = true;
  582. badPoints[i+2][j+2] = true;
  583.  
  584. resultImage[i+1][j+1] = MedianColor(i+1, j+1, false);
  585. resultImage[i+2][j+2] = MedianColor(i+2, j+2, false);
  586.  
  587. badPoints[i+1][j+1] = false;
  588. badPoints[i+2][j+2] = false;
  589. }
  590. }
  591. }
  592. }
  593.  
  594. void Filter2x2Linear(int centerThres, int aroundThres, bool centerLighter)
  595. {
  596. int a = 1, b = -1;
  597.  
  598. if (!centerLighter)
  599. {
  600. a = -a;
  601. b = -b;
  602. }
  603.  
  604. int matrHor [3][4] = { {1, 1, 1, 1}, {1, 0, 0, 1}, {1, 1, 1, 1}};
  605. int matrVer [4][3] = { {1, 1, 1}, {1, 0, 1}, {1, 0, 1}, {1, 1, 1}};
  606.  
  607. for (int i=-1; i<=h-2; i++)
  608. for (int j=-1; j<=w-3; j++)
  609. {
  610. // Hor
  611. //
  612. if (abs((int)resultImage[i+1][j+1] - (int)resultImage[i+1][j+2]) <= centerThres)
  613. {
  614. int center = ((int)resultImage[i+1][j+1] + (int)resultImage[i+1][j+2]) / 2;
  615.  
  616. bool apply = true;
  617.  
  618. for (int ii=0; ii<3; ii++)
  619. {
  620. for (int jj=0; jj<4; jj++)
  621. if (((ii + i) >= 0) && ((ii + i) < h) && ((jj + j) >= 0) && ((jj + j) < w))
  622. if ((matrHor[ii][jj] == 1) &&
  623. ((a*center + (int)b*resultImage[i+ii][j+jj]) < aroundThres))
  624. {
  625. apply = false;
  626. break;
  627. }
  628.  
  629. if (!apply) break;
  630. }
  631.  
  632. if (apply)
  633. {
  634. badPoints[i+1][j+1] = true;
  635. badPoints[i+1][j+2] = true;
  636.  
  637. resultImage[i+1][j+1] = MedianColor(i+1, j+1, false);
  638. resultImage[i+1][j+2] = MedianColor(i+1, j+2, false);
  639.  
  640. badPoints[i+1][j+1] = false;
  641. badPoints[i+1][j+2] = false;
  642. }
  643. }
  644. }
  645.  
  646. for (int i=-1; i<=h-3; i++)
  647. for (int j=-1; j<=w-2; j++)
  648. {
  649. // Ver
  650. //
  651. if (abs((int)resultImage[i+1][j+1] - (int)resultImage[i+2][j+1]) <= centerThres)
  652. {
  653. int center = ((int)resultImage[i+1][j+1] + (int)resultImage[i+2][j+1]) / 2;
  654.  
  655. bool apply = true;
  656.  
  657. for (int ii=0; ii<4; ii++)
  658. {
  659. for (int jj=0; jj<3; jj++)
  660. if (((ii + i) >= 0) && ((ii + i) < h) && ((jj + j) >= 0) && ((jj + j) < w))
  661. if (( matrVer[ii][jj] == 1) &&
  662. ((a*center + (int)b*resultImage[i+ii][j+jj]) < aroundThres))
  663. {
  664. apply = false;
  665. break;
  666. }
  667.  
  668. if (!apply) break;
  669. }
  670.  
  671. if (apply)
  672. {
  673. badPoints[i+1][j+1] = true;
  674. badPoints[i+2][j+1] = true;
  675.  
  676. resultImage[i+1][j+1] = MedianColor(i+1, j+1, false);
  677. resultImage[i+2][j+1] = MedianColor(i+2, j+1, false);
  678.  
  679. badPoints[i+1][j+1] = false;
  680. badPoints[i+2][j+1] = false;
  681. }
  682. }
  683. }
  684. }
  685.  
  686. void Filter2x2()
  687. {
  688. Filter2x2Diagonal(8, 35, false);
  689. Filter2x2Diagonal(8, 35, true);
  690.  
  691. Filter2x2Linear(8, 35, false);
  692. Filter2x2Linear(8, 35, true);
  693. }
  694.  
  695. int main(void)
  696. {
  697. int t;
  698.  
  699. scanf("%d", &t);
  700.  
  701. for (int tt=0; tt<t; tt++)
  702. {
  703. ClearBadPoints();
  704.  
  705. scanf("%d %d %d", &q, &h, &w);
  706.  
  707. ReadImage();
  708.  
  709. diffcount = 0;
  710. CopySourceToResult();
  711.  
  712. int thres = 14 - q/2;
  713. /*
  714. do
  715. {
  716. ClearBadPoints();
  717. diffcount = 0;
  718. CopyResultToSource();
  719. FilterSinglePoints(thres);
  720. ApplyDiffs();
  721. } while (diffcount > 3);
  722. */
  723.  
  724. // Some filter
  725. ClearBadPoints();
  726. diffcount = 0;
  727. CopyResultToSource();
  728.  
  729. int diffthres = 120;
  730. int samethres = 0;//12 - q/2;
  731. if (samethres < 0) samethres = 0;
  732.  
  733. //Filter(diffthres, samethres);
  734. //ApplyDiffs();
  735. do
  736. {
  737. ClearBadPoints();
  738. diffcount = 0;
  739. CopyResultToSource();
  740. FilterSinglePoints(thres+1);
  741. ApplyDiffs();
  742. } while (diffcount > 3);
  743. // It's ok
  744. FillLines(h+w <= 100);
  745. FillLines(h+w <= 100);
  746. FillLines(h+w <= 100);
  747.  
  748. // It's ok too
  749. Filter2x2();
  750. if (q > 3)
  751. do
  752. {
  753. ClearBadPoints();
  754. diffcount = 0;
  755. CopyResultToSource();
  756. FilterSinglePoints(thres);
  757. ApplyDiffs();
  758. } while (diffcount > 3);
  759.  
  760. /*
  761. if ((h == 100) && (w == 100))
  762. {
  763. FilterAvatar(10);
  764. }
  765. */
  766.  
  767. if (tt > 0) printf("\n");
  768.  
  769. WriteImage();
  770. }
  771. }