ens-ulm-1

google hashcode 2014 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1/
Log | Files | Refs

main.cc (2175B)

      1 #include <cstdio>
      2 #include <vector>
      3 #include <algorithm>
      4 
      5 using namespace std;
      6 
      7 const int Tm = 3000 ;
      8 char grid[Tm][Tm] ;
      9 int Tx,Ty ;
     10 
     11 int cx,cy,ct,nb;
     12 int nbBlancs[Tm][Tm] ;
     13 int nbNoirs[Tm][Tm] ;
     14 std::vector<int> out[3];
     15 std::vector<int> er[2];
     16 
     17 
     18 int nbt(int t[][Tm],int x, int y,int c)
     19 {
     20   return t[y][x]+t[y+c][x+c]-t[y][x+c]-t[y+c][x] ;
     21 }
     22 
     23 int get(int t[][Tm],char c,int x, int y)
     24 {
     25   if(x>Tx||y>Ty)
     26     return 0;
     27   if(t[y][x]==-1)
     28     {
     29       int a = get(t,c,x+1,y+1);
     30       int b = get(t,c,x,y+1);
     31       int d = get(t,c,x+1,y);
     32       t[y][x] = b+d-a+(grid[y][x]==c) ;
     33     }
     34   return t[y][x];
     35 }
     36 
     37 bool get_carre ()
     38 {
     39   fill(nbBlancs[0],nbBlancs[Tm],-1);
     40   fill(nbNoirs[0],nbNoirs[Tm],-1);
     41   get(nbBlancs,'.',0,0);
     42   get(nbNoirs,'#',0,0);
     43   nb = 0 ;
     44   for(int y = 0 ; y < Ty ; y++ )
     45     for(int x = 0 ; x < Tx ; x++ )
     46       {
     47 	int c = 1 ;
     48 	while(nbt(nbBlancs,x,y,c)==0 && x+c<=Tx && y+c<=Ty)
     49 	  c+=2 ;
     50 	if(x+c<=Tx && y+c<=Ty)
     51 	  if(nbt(nbBlancs,x,y,c)<3 && nbt(nbNoirs,x,y,c) > nbt(nbNoirs,x,y,c-2)+3)
     52 	    {
     53 	      for(int rx = x ; rx < x+c ; rx++ )
     54 		for(int ry = y ; ry < y+c ; ry++ )
     55 		  if(grid[ry][rx] = '.')
     56 		    {		    
     57 		      er[0].push_back(ry);
     58 		      er[1].push_back(rx);
     59 		    }
     60 	      c+= 2; 
     61 	    }
     62 	c-=2;
     63 	if(c>0)
     64 	  {
     65 	    int nbN = nbt(nbNoirs,x,y,c); 
     66 	    if(nbN>nb)
     67 	      {
     68 		nb = nbN ;
     69 		cx = x ;
     70 		cy  = y ;
     71 		ct = c ;
     72 	      }
     73 	  }
     74       }
     75   return nb>1;
     76 }
     77 
     78 int main()
     79 {
     80   scanf("%d %d",&Ty,&Tx);
     81   for(int l = 0 ; l < Ty ; l++)
     82     scanf("%s",grid[l]);
     83   while(get_carre())
     84     {
     85       fprintf(stderr,"%d / %d / %d\n",nb,nbNoirs[0][0],out[0].size());
     86       out[0].push_back(cy);
     87       out[1].push_back(cx);
     88       out[2].push_back(ct);
     89       for(int x = cx ; x < cx+ct ; x++ )
     90 	for(int y = cy ; y < cy+ct ; y++ )
     91 	  grid[y][x] = '-';
     92     }
     93   //  printf("%d\n",out[0].size()+nbNoirs[0][0]);
     94 
     95   for(int x = 0 ; x < Tx ; x++ )
     96     for(int y = 0 ; y < Ty ; y++ )
     97       if(grid[y][x]=='#')
     98 	printf("PAINTSQ %d %d %d\n",y,x,1);
     99 	
    100   for(size_t i = 0 ; i < out[0].size() ; i++ )
    101     printf("PAINTSQ %d %d %d\n",out[0][i],out[1][i],out[2][i]);
    102   for(size_t i = 0 ; i < er[0].size() ; i++ )
    103     printf("ERASECELL %d %d",er[0][i],er[1][i]);
    104   return 0;
    105 }