Question

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 --> #726 Acoperire1 pbinfo (va rog ajutor am nevoie de 100 de pct.)

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
6

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

Answer 1

#include<bits/stdc++.h>

using namespace std;

ifstream fin("acoperire1.in");
ofstream fout("acoperire1.out");

int n,k,x[210][210],u,v,

C[6][6]={
    {0,1,1,1,2,0},
    {3,3,3,1,2,4},
    {5,5,3,2,2,4},
    {5,6,6,7,4,4},
    {5,6,8,7,7,7},
    {0,6,8,8,8,0}},
    
D[6][6]={
    {0,0,1,1,1,2},
    {0,3,1,2,2,2},
    {4,3,3,3,5,5},
    {4,4,4,6,6,5},
    {7,7,7,8,6,5},
    {7,8,8,8,6,0}},
    
O[4][5]={
    {1,1,1,2,0},
    {0,3,1,2,4},
    {0,3,2,2,4},
    {0,3,3,4,4}},
    
V[5][4]={
    {1,0,0,0},
    {1,2,2,2},
    {1,1,3,2},
    {3,3,3,4},
    {0,4,4,4}},
    
R[4][4]={
    {1,1,1,2},
    {1,2,2,2},
    {3,3,3,4},
    {3,4,4,4}};

void COLT(int,int),DIAG(int,int),ORIZ(int,int),VERT(int,int),REST(int,int);
int main()
{
    
    int i,j;
    
    fin >> n;
    
    if(n%4!=2)
    {
        fout << -1;
        return 0;
    }
    
    COLT(1,1);
    
    for(i=5;i<n-1;i+=4)
        DIAG(i,i);
    for(j=6;j<n;j+=4)
        ORIZ(1,j);
    for(i=6;i<n;i+=4)
        VERT(i,1);
    for(i=2;i<n;i++)
        for(j=2;j<n;j++)
            if(!x[i][j])
                REST(i,j);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<n;j++)
            fout << x[i][j] << " ";
        fout << x[i][j] << endl;
    }
    
    return 0;

}

void COLT(int i,int j)
{
    for(u=0;u<6;u++)
        for(v=0;v<6;v++)
            if(C[u][v])
                x[i+u][j+v]=k+C[u][v];
        k+=8;
}
void DIAG(int i,int j)
{
    for(u=0;u<6;u++)
        for(v=0;v<6;v++)
            if(D[u][v])
                x[i+u][j+v]=k+D[u][v];
        k+=8;
}
void ORIZ(int i,int j)
{
    for(u=0;u<4;u++)
        for(v=0;v<5;v++)
            if(O[u][v])
                x[i+u][j+v]=k+O[u][v];
        k+=4;
}
void VERT(int i,int j)
{
    for(u=0;u<5;u++)
        for(v=0;v<4;v++)
            if(V[u][v])
                x[i+u][j+v]=k+V[u][v];
        k+=4;
}
void REST(int i,int j)
{
    for(u=0;u<4;u++)
        for(v=0;v<4;v++)
            if(R[u][v])
                x[i+u][j+v]=k+R[u][v];
        k+=4;
}