Назад к лучшим решениям Status: AC, problem ZDIP, contest ZEL07. By majac (Andrey Maksimenko), 2007-03-13 13:29:07.
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4.  
  5.  
  6. //#define DEBUG_DATA_OUT 1
  7.  
  8. #define MAX_WIDTH 200
  9. #define MAX_HEIGHT 200
  10. #define FILT_RAD 2
  11. int Q,H,W;
  12. int weight[5][5] = { { 0,1,2,1,0 },
  13.                      { 1,5,8,5,1 },
  14.                      { 2,8,10,8,2 },
  15.                      { 1,5,8,5,1 },
  16.                      { 0,1,2,1,0 }
  17.                    };
  18. #define IMGVAL_MAX 256
  19. #define NOISEVAL_MAX 1000
    20. 

  20.  
  21. int img[200][200];
  22. int noise[200][200];
  23. int noise1[200][200];
  24. int noise_hit[200][200];
  25.  
  26. int noiselev_cnt[NOISEVAL_MAX];
  27.  
  28. #define SIM_DELTA 20
  29. #define DIF_DELTA 70
  30. #define VALID_TRESHOLD 600
  31.  
  32. void print_arr(int *arr,int Width, int Height)
  33. { int i,j;
  34.   
  35.   for (j=0; j<Height; j++)
  36.   { for (i=0; i<Width; i++)
  37.       printf("%3d ",arr[MAX_WIDTH*j+i]);
  38.     printf("\n");
  39.   }    
  40. }
  41.  
  42. __inline int abs(int val)
    43. 

  43. { return val < 0 ? -val : val;
  44. }
  45.  
  46.  
  47. void highpass(int expected,int *filtlev)
  48. { int total = 0;
  49.   int lev = 0;
  50.   
  51.   #ifdef DEBUG_DATA_OUT 
  52.     printf("HIGHPASS  expected = %d\n",expected);
  53.   #endif
  54.   for (lev=999; lev>=0 && total*100 < expected ; lev--)
  55.   { total += noiselev_cnt[lev];
  56.     /*#ifdef DEBUG_DATA_OUT 
  57.     printf("lev = %d  cnt = %d   |  total = %d\n",lev,noiselev_cnt[lev],total);
  58.     #endif*/
  59.   }
  60.   if ( total*100 > expected )
  61.     lev++;
  62.   if (lev<0)
  63.     lev = 0;
  64.   *filtlev = lev;
  65.   #ifdef DEBUG_DATA_OUT 
  66.     printf("HIGHPASS  filtlev = %d\n",lev);
  67.   #endif
  68. }
  69.  
  70. void colregion_hit(int regstart,int regwidth,int Width,int Height)
  71. { int i,j;
  72.   int expected,filtlev;
  73.   
  74.   #ifdef DEBUG_DATA_OUT 
  75.     printf("COLREGION_HIT  regstart = %d  regwidth = %d\n",regstart,regwidth);
  76.   #endif
  77.   
  78.   
  79.   memset(noiselev_cnt,0,sizeof(noiselev_cnt));
  80.   for (j=0; j<Height; j++)
    81. 

  81.   { for (i=0; i<Width; i++)
  82.     { if ( img[j][i]>= regstart && img[j][i]<= regstart+regwidth )
  83.       { noiselev_cnt[noise[j][i]]++;
  84.       }
  85.     }
  86.   }
  87.   
  88.   expected = H*W*Q*regwidth/IMGVAL_MAX;
  89.   highpass(expected,&filtlev);
  90.   
  91.   for (j=0; j<Height; j++)
  92.   { for (i=0; i<Width; i++)
  93.     { if ( img[j][i]>= regstart && img[j][i]<= regstart+regwidth )
  94.       { noise_hit[j][i]++;
  95.         if ( noise[j][i] > filtlev )
  96.           noise1[j][i] += noise[j][i];
  97.         else if ( noise[j][i] > 2*filtlev/3 )
  98.           noise1[j][i] += noise[j][i] - 2*filtlev/3;
  99.       }
  100.     }
  101.   }
  102. }
  103.  
  104. void colregion(int Width,int Height)
  105. { int size,k;
  106.   
  107.   memset(noise1,0,sizeof(noise1));
  108.   memset(noise_hit,0,sizeof(noise_hit));
  109.   size = 15;
  110.   for (k=0; k+size < IMGVAL_MAX; k+= size+1)
  111.   { colregion_hit(k,size,Width,Height);
  112.   }
  113. }
  114.  
    115. 

  115.  
  116. int gaussfilter(int x,int y,int *estval,int *valid,int *nsim,int *ndif)
  117. { int i,j;
  118.   int estimate = 0, importance = 0, weightsum = 0;
  119.   int est_valid = 0, center_valid;
  120.   int thisval,neighval;
  121.   int imp, wght;
  122.   int centerimp;
  123.   
  124.   *ndif = 0; *nsim = 0;
  125.   thisval = img[y][x];
  126.   for ( j=-FILT_RAD; j<=FILT_RAD; j++ )
  127.   { if ( y+j >= 0 && y+j < MAX_HEIGHT )  
  128.       for ( i=-FILT_RAD; i<=FILT_RAD; i++ )
  129.       { if ( x+i >= 0  && x+i < MAX_WIDTH )
  130.         { neighval = img[y+j][x+i];
  131.           wght = weight[j+FILT_RAD][i+FILT_RAD];
  132.           weightsum += wght;
  133.           imp = wght* ( NOISEVAL_MAX - noise[y+j][x+i] ); 
  134.           importance += imp;
  135.           estimate += imp*neighval;
  136.           if ( ! (i==0 && j==0) )
  137.             if ( NOISEVAL_MAX - noise[y+j][x+i] > VALID_TRESHOLD )
  138.             { if ( abs(thisval-neighval) < SIM_DELTA )
  139.                 (*nsim) +=100*wght;
  140.               if ( abs(thisval-neighval) > DIF_DELTA )
  141.                 (*ndif) +=100*wght;
  142.             }
  143.         }  
  144.       }
  145.   }
  146.     
  147.   //&#1074;&#1099;&#1095;&#1080;&#1089;&#1083;&#1103;&#1077;&#1084; &#1074;&#1082;&#1083;&#1072;&#1076; &#1094;&#1077;&#1085;&#1090;&#1088;&#1072;&#1083;&#1100;&#1085;&#1086;&#1081; &#1090;&#1086;&#1095;&#1082;&#1080; &#1074; &#1091;&#1082;&#1072;&#1079;&#1072;&#1085;&#1085;&#1099;&#1077; &#1089;&#1091;&#1084;&#1084;&#1099;
    148. 

  148.   wght = weight[0+FILT_RAD][0+FILT_RAD];
  149.   centerimp = wght* ( NOISEVAL_MAX - noise[y][x] );
  150.   
  151.   weightsum -= wght;
  152.   importance -= centerimp;
  153.   estimate -= centerimp*img[y][x];
  154.   estimate /= importance;
  155.   *nsim /= weightsum;
  156.   *ndif /= weightsum;
  157.   
  158.   est_valid = importance/weightsum;
  159.   center_valid = NOISEVAL_MAX - noise[y][x];
  160.   *estval = estimate;
  161.   *valid = est_valid;
  162.   return 1;  
  163. }
  164.  
  165. int main()
  166. { int Ntest,test,pass;
  167.   int x,y;
  168.   int filtered,diff,filt_valid,cent_valid,nsim,ndif;
  169.   int filtlev,expected,total;
  170.   
  171.   scanf("%d",&Ntest);
  172.   for (test=1; test<=Ntest; test++)
  173.   { scanf("%d %d %d",&Q,&H,&W);
  174.     expected = Q*H*W;
  175.     
  176.     
  177.     for (y=0; y<H; y++)
  178.       for (x=0; x<W; x++)
    179. 

  179.       { scanf("%d",&(img[y][x]));
  180.       }
  181.     
  182.     memset(noise,0,sizeof(noise));
  183.     memset(noise1,0,sizeof(noise1));
  184.         
  185.     for (pass=0; pass<5; pass++)
  186.     { 
  187.       #ifdef DEBUG_DATA_OUT 
  188.       printf("PASS NUMBER   %d\n",pass);
  189.       #endif
  190.       memset(noiselev_cnt,0,sizeof(noiselev_cnt));
  191.       for (y=0; y<H; y++)
  192.       { for (x=0; x<W; x++)
    193. 

  193.         { gaussfilter(x,y,&filtered,&filt_valid,&nsim,&ndif);
  194.           cent_valid = NOISEVAL_MAX-noise[y][x];
  195.           
  196.           diff = abs(filtered-img[y][x]);
  197.           #ifdef DEBUG_DATA_OUT 
  198.           printf("%d %d v(%d %d) n(%d %d)  ",filtered,noise[y][x],filt_valid,cent_valid,nsim,ndif);
  199.           #endif
  200.           if (nsim < 30)
  201.             noise1[y][x] = (30-nsim)*25 + diff;
  202.           if (ndif > 85) 
  203.             noise1[y][x] += (100-ndif)*30 + diff;
  204.           if (noise1[y][x]<0)
  205.             noise1[y][x] = 0;   
  206.           if (noise1[y][x]>=NOISEVAL_MAX)
  207.             noise1[y][x] = NOISEVAL_MAX-1;
  208.                    
  209.           noiselev_cnt[noise1[y][x]]++;
  210.         }
  211.         #ifdef DEBUG_DATA_OUT 
  212.         printf("\n");
  213.         #endif
  214.       }
  215.       
  216.       
  217.       #ifdef DEBUG_DATA_OUT 
  218.       printf("NOISE1 before COLREGION\n");
  219.       print_arr(&(noise1[0][0]),W,H);
  220.       #endif
    221. 

  221.       
  222.       memcpy(noise,noise1,sizeof(noise1));
  223.       memset(noise1,0,sizeof(noise1));
  224.       
  225.       
  226.       colregion(W,H);
  227.       #ifdef DEBUG_DATA_OUT 
  228.       printf("NOISE1 after COLREGION\n");
  229.       print_arr(&(noise1[0][0]),W,H);
  230.       #endif
  231.       
  232.       
  233.       /*
  234.       #ifdef DEBUG_DATA_OUT 
  235.       printf("NOISE1 before HIGH_PASS_FILTER\n");
  236.       print_arr(&(noise1[0][0]),W,H);
  237.            
  238.       printf("expected = %d\n",expected);
  239.       #endif
  240.       
  241.       total = 0;
  242.       for (filtlev=999; filtlev>=0 && total*100 < expected ; filtlev--)
  243.       { total += noiselev_cnt[filtlev];
  244.         #ifdef DEBUG_DATA_OUT 
  245.         printf("lev = %d  cnt = %d   |  total = %d\n",filtlev,noiselev_cnt[filtlev],total);
  246.         #endif
  247.       }
  248.       if ( total*100 > expected )
  249.         filtlev++;
  250.       if (filtlev<0)
  251.         filtlev = 0;
  252.       
  253.       for (y=0; y<H; y++)
    254. 

  254.       { for (x=0; x<W; x++)
  255.         { if (noise1[y][x]<=filtlev)
  256.             noise1[y][x]=0;
  257.         }
  258.       }
  259.       #ifdef DEBUG_DATA_OUT  
  260.       printf("NOISE1 after HIGH_PASS_FILTER\n");
  261.       print_arr(&(noise1[0][0]),W,H);
  262.       #endif
  263.       */  
  264.     
  265.       memcpy(noise,noise1,sizeof(noise1));
  266.       memset(noise1,0,sizeof(noise1));
  267.     }
  268.     
  269.     printf("%d %d\n",H,W);
  270.     for (y=0; y<H; y++)
  271.     { for (x=0; x<W; x++)
  272.       { if ( noise[y][x] > 50 )
    273. 

  273.         { gaussfilter(x,y,&filtered,&filt_valid,&nsim,&ndif);
  274.           printf("%d ",filtered);
  275.         }
  276.         else
  277.           printf("%d ",img[y][x]);
  278.       }
  279.       printf("\n");
  280.     }
  281.     
  282.   }
  283.  
  284.   return 0;
  285. }