Cod sursa(job #166113)

Utilizator floringh06Florin Ghesu floringh06 Data 27 martie 2008 14:18:33
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 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;   
    }