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

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

#include<fstream>
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;
}