Dintr-o suprafaţă pătrată cu latura de N unităţi care este formată din N*N pătrăţele cu latura de o unitate se decupează cele 4 pătrăţele din colţuri.

Cerința

Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie 4 unităţi care au forma următoare:

Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele 8 moduri de a le aşeza.

Date de intrare

Fișierul de intrare acoperire1.in conține pe prima linie un număr natural N, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire acoperire1.out va conține valoarea -1 pe prima linie dacă problema nu are soluţie, iar în caz contrar va avea următoarea structură: N linii cu câte N valori fiecare reprezentând codificarea suprafeţei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu. Poziţiile ocupate de prima piesă aşezată se vor codifica cu 1, poziţiile ocupate de a doua piesă aşezată se vor codifica cu 2 etc. Corespunzător colţurilor lipsă se va scrie valoarea 0.

Restricții și precizări

6 ≤ n ≤ 200
Piesele trebuie să fie complet în interiorul zonei;
Zona trebuie acoperită integral;
Două piese nu se pot suprapune complet sau parţial;

Exemplu

acoperire1.in

acoperire1.out

0 7 2 2 2 0 
3 7 2 4 4 4 
3 7 7 4 5 5 
3 3 6 1 1 5 
6 6 6 8 1 5 
0 8 8 8 1 0

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Acoperire1:

#include <stdio.h>
#define DIM 210

int A[DIM][DIM];

int N, i, j, k, ii, jj, L, p;


int sase[6][6] = {
    {0,1,1,2,2,0},
    {6,6,1,2,8,8},
    {5,6,1,2,7,8},
    {5,6,3,4,7,8},
    {5,5,3,4,7,7},
    {0,3,3,4,4,0}
};


int main (){

    FILE *f = fopen("acoperire1.in","r");
    FILE *g = fopen("acoperire1.out","w");
    fscanf(f,"%d",&N);
    
    if (N%4!=2) {
        fprintf(g,"-1");
        fclose(g);
        return 0;
    }
    fclose(f);
    
    
    i = N/2 - 2;
    for (ii=0;ii<6;ii++)
        for (jj=0;jj<6;jj++)
            A[i+ii][i+jj] = sase[ii][jj];
    for (i-=2, L = 10, p = 8;i>0;i-=2, L+=4) {
        A[i][i+1] = A[i][i+2] = A[i+1][i+2] = A[i+2][i+2] = ++p;
        j = i+L-1;
        A[i][j-1] = A[i][j-2] = A[i+1][j-2] = A[i+2][j-2] = ++p;
        k = i + L - 1;
        A[k][i+1] = A[k][i+2] = A[k-1][i+2] = A[k-2][i+2] = ++p;
        A[k][j-1] = A[k][j-2] = A[k-1][j-2] = A[k-2][j-2] = ++p;
    
        for (ii = i+3; ii<j-4; ii+=4) {
            A[i+1][ii] = A[i][ii] = A[i][ii+1] = A[i][ii+2] = ++p;
            A[i+1][ii+1] = A[i+1][ii+2] = A[i+1][ii+3] = A[i][ii+3] = ++p;
            
            A[k-1][ii] = A[k][ii] = A[k][ii+1] = A[k][ii+2] = ++p;
            A[k-1][ii+1] = A[k-1][ii+2] = A[k-1][ii+3] = A[k][ii+3] = ++p;
        }
    
        for (ii = i+1; ii<k; ii+=4) {
            A[ii][i+1] = A[ii][i] = A[ii+1][i] = A[ii+2][i] = ++p;
            A[ii+1][i+1] = A[ii+2][i+1] = A[ii+3][i+1] = A[ii+3][i] = ++p;
            
            A[ii][j-1] = A[ii][j] = A[ii+1][j] = A[ii+2][j] = ++p;
            A[ii+1][j-1] = A[ii+2][j-1] = A[ii+3][j-1] = A[ii+3][j] = ++p;
        }   
    }
    
    for (i=1;i<=N;i++){
        for (j=1;j<=N;j++)
            fprintf(g,"%d ",A[i][j]);
        fprintf(g,"
");
    }
    
    fclose(g);
    
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #726 Acoperire1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #726 Acoperire1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #726 Acoperire1