Cod sursa(job #1972429)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 23 aprilie 2017 09:39:18
Problema Piese Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <bits/stdc++.h>
#include <cmath>

using namespace std;

int tabla[502][505];
int n, m;

int Putere(int a, int b){

   if(b == 0){
        return 1;
   }

    int c = 1;

    while( b ){
        c *= a;
        b--;
    }

    return c;

}

bool OK(int x, int y){

    if(x < 0 || y < 0 || x >= n || y >= m){
        return false;
    }
    if(tabla[x][y] != 0){
        return false;
    }

    return true;
}

void desenare(int x, int y, int corner, int Size, int no){
    if(corner == 1){
        for(int i = x, cont = 0; cont < Size; i++, cont++){
            for(int j = y, cont1 = 0; cont1 < Size; j++, cont1++){
                tabla[i][j] = no;
            }
        }
    }

    if(corner == 2){
        y -= Size - 1;
        for(int i = x, cont = 0; cont < Size; i++, cont++){
            for(int j = y, cont1 = 0; cont1 < Size; j++, cont1++){
                tabla[i][j] = no;
            }
        }
    }

    if(corner == 3){
        y -= Size - 1;
        x -= Size - 1;
        for(int i = x, cont = 0; cont < Size; i++, cont++){
            for(int j = y, cont1 = 0; cont1 < Size; j++, cont1++){
                tabla[i][j] = no;
            }
        }
    }

    if(corner == 4){
        x -= Size - 1;
        for(int i = x, cont = 0; cont < Size; i++, cont++){
            for(int j = y, cont1 = 0; cont1 < Size; j++, cont1++){
                tabla[i][j] = no;
            }
        }
    }
}

int aplicare(int x, int y, int Size){
    bool a;
    int x1, y1;

    for(int i = 1; i <= 4; i++){
        a = true;

        if(i == 1){
            x1 = x; y1 = y;
        }

        if(i == 2){
            y1 = y - (Size - 1);
        }

        if(i == 3){
            x1 = x - (Size - 1);
            y1 = y - (Size - 1);
        }

        if(i == 4){
            x1 = x - (Size - 1);
        }

        for(int j = x1, c = 0; c < Size && a; c++, j++)
            for(int k = y1, c1 = 0; c1 < Size && a; c1++,k++)
                if( !OK(j, k) )
                    a = false;

        if( a ){
            return i;
        }
    }

    return -1;
}

int main()
{

    ifstream in("piese.in");
    ofstream out("piese.out");

    in>>n>>m;

    int putere = log( min(n, m) )/log(2);

   int aux = 0, num = 1, val;
    bool found;
    while( putere >= 1 ){

        found = false;
        val = Putere(2, putere);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){

                aux = aplicare(i, j, val);
                if(aux != -1){
                    desenare(i, j, aux, val, num);
                    found = true;
                    num++;
                    i = 0; j = -1;
                }

            }
        }

        if( !found ){
            putere--;
        }

    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(tabla[i][j] == 0){
                tabla[i][j] = num++;
            }
        }
    }

    out<<num - 1<<"\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            out<<tabla[i][j]<<" ";
        }
        out<<"\n";
    }

    return 0;
}