ens-ulm-1

commit 878240e97fe8f7b40e94bcc57fcf724fa713df37
parent ee07c07c16831385712e8e498c5fba1d1ac55666
Author: Jachiet Louis <louis@jachiet.com>
Date:   Fri,  4 Apr 2014 21:24:44 +0200

test

Diffstat:
training/louis/in
 | 
3
+++
training/louis/main.cc
 | 
77
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 80 insertions(+), 0 deletions(-)
diff --git a/training/louis/in b/training/louis/in
@@ -0,0 +1,3 @@
+2 2
+..
+.#
diff --git a/training/louis/main.cc b/training/louis/main.cc
@@ -0,0 +1,77 @@
+#include <cstdio>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+const int Tm = 3000 ;
+char grid[Tm][Tm] ;
+int Tx,Ty ;
+
+int cx,cy,ct,nb;
+int nbBlancs[Tm][Tm] ;
+int nbNoirs[Tm][Tm] ;
+std::vector<int> out[3];
+
+int get(int t[][Tm],char c,int x, int y)
+{
+  if(x>Tx||y>Ty)
+    return 0;
+  if(t[y][x]==-1)
+    {
+      int a = get(t,c,x+1,y+1);
+      int b = get(t,c,x,y+1);
+      int d = get(t,c,x+1,y);
+      t[y][x] = b+d-a+(grid[y][x]==c) ;
+    }
+  return t[y][x];
+}
+
+bool get_carre ()
+{
+  fill(nbBlancs[0],nbBlancs[Tm],-1);
+  fill(nbNoirs[0],nbNoirs[Tm],-1);
+  get(nbBlancs,'.',0,0);
+  get(nbNoirs,'#',0,0);
+  nb = 0 ;
+  for(int y = 0 ; y < Ty ; y++ )
+    for(int x = 0 ; x < Tx ; x++ )
+      {
+	int c = 1 ;
+	while(nbBlancs[y+c][x+c]+nbBlancs[y][x]-nbBlancs[y+c][x]-nbBlancs[y][x+c] == 0 && x+c<=Tx && y+c<=Ty)
+	  c+=2 ;
+	c-=2;
+	if(c>0)
+	  {
+	    int nbN = (nbNoirs[y+c][x+c]+nbNoirs[y][x]-nbNoirs[y+c][x]-nbNoirs[y][x+c]); 
+	    if(nbN>nb)
+	      {
+		nb = nbN ;
+		cx = x ;
+		cy  = y ;
+		ct = c ;
+	      }
+	  }
+      }
+  return nb>0;
+}
+
+int main()
+{
+  scanf("%d %d",&Ty,&Tx);
+  for(int l = 0 ; l < Ty ; l++)
+    scanf("%s",grid[l]);
+  while(get_carre())
+    {
+      out[0].push_back(cx);
+      out[1].push_back(cy);
+      out[2].push_back(ct);
+      for(int x = cx ; x < cx+ct ; x++ )
+	for(int y = cy ; y < cy+ct ; y++ )
+	  grid[y][x] = '-';
+    }
+  printf("%d\n",out[0].size());
+  for(size_t i = 0 ; i < out[0].size() ; i++ )
+    printf("PAINTSQ %d %d %d\n",out[0][i],out[1][i],out[2][i]);
+  return 0;
+}