Cod sursa(job #127999)

Utilizator floringh06Florin Ghesu floringh06 Data 25 ianuarie 2008 19:24:16
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#include <string.h>

using namespace std;

#define FIN "piese.in"
#define FOUT "piese.out"
#define MAX_N 505

int A[MAX_N][MAX_N];
int n, m, ct, ac;

    void cover (int x1, int y1, int x2, int y2)
    {
         int lat;
         lat = 1;
         while (lat << 1 <= x2 - x1 + 1 && lat << 1 <= y2 - y1 + 1) lat <<= 1;
         
         int i, j;
         ++ct;
         ac += (lat * lat);
         for (i = x1; i <= x1 + lat - 1; ++i)
             for (j = y1; j <= y1 + lat - 1; ++j)
                 A[i][j] = ct;
         
	     if (ac == n * m) return;
	     if (x1 + lat <= n && y1 + lat - 1 <= m && !A[x1 + lat][y1] && !A[x2][y1 + lat - 1])
	        cover (x1 + lat, y1, x2, y1 + lat - 1);
         if (ac == n * m) return;
         if (y1 + lat <= m && !A[x1][y1 + lat] && !A[x2][y2])
	        cover (x1, y1 + lat, x2, y2);
    }
         
    void print ()
    {
         int i, j;
         printf ("%d\n", ct);
         for (i = 1; i <= n; ++i)
         {
             for (j = 1; j <= m; ++j)
                 printf ("%d ", A[i][j]);
             printf ("\n");
         }
    }     
    
    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d", &n, &m);
        
        cover (1, 1, n, m);
        print ();
        
        return 0;
    }