Cod sursa(job #461278)

Utilizator SpiderManSimoiu Robert SpiderMan Data 6 iunie 2010 10:33:26
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

const char FIN[] = "piese.in", FOU[] = "piese.out";
const int MAX = 505;

int put[] = { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 } ;

short rez[MAX][MAX];

int N, M, sol ;

inline int min ( int a, int b )
{
    if ( a < b ) return a;
    return b;
}

int search ( int X )
{
    int i;

    for (i = 0; put[i] <= X; ++i);

    return i - 1;
}

void fun (int x1, int y1, int x2, int y2)
{
    if ( x2 < x1 || y2 < y1 )
        return ;

    int ax = search ( min ( x2 - x1 + 1 , y2 - y1 + 1 ) );

    ++sol;
    for (int i = x1; i < x1 + ( 1 << ax ) ; ++i)
        for (int j = y1; j < y1 + ( 1 << ax ) ; ++j)
            rez[i][j] = sol;

    fun ( x1 , y1 + ( 1 << ax ) , x1 + ( 1 << ax ) - 1 , y2 ) ;
    fun ( x1 + ( 1 << ax ) , y1 , x2 , y2 ) ;
}

int main ()
{
    freopen (FIN , "r" , stdin);
    freopen (FOU , "w" , stdout);

    scanf ("%d %d", &N, &M);

    fun (1 , 1 , N , M);

    printf ("%d\n", sol);

    for (int i = 1; i <= N; ++i, printf ("\n"))
        for (int j = 1; j <= M; ++j)
            printf ("%hd ", rez[i][j]) ;

    return 0;
}