Cerința

Considerăm o tablă de șah pătratică formată din 2n linii și 2n coloane, unde n este un număr natural nenul, formată din 2n*2n zone. Aceasta poate fi acoperită, cu excepția unei singure zone, cu piese în formă de L, fiecare piesă acoperind 3 zone. De exemplu, pentru n=2, o acoperire este următoarea, în care zona neagră este cea neacoperită de piese:

Pentru n dat, determinați o modalitate de acoperire a tablei cu piese, astfel încât să nu se suprapună piesele și să rămână o singură zonă neacoperită.

Date de intrare

Programul citește de la tastatură numărul n

Date de ieșire

Programul va afișa pe ecran o matrice care reprezintă tabla, cu următoarele proprietăți:

• matricea va avea 2n linii și 2n coloane
• matricea va conține un singur element 0, reprezentând zona neacoperită
• fiecare piesă va fi marcată pe tablă prin trei elemente cu aceeași valoare, dispuse în formă de L
• oricare două piese de pe tablă vor fi marcate cu valori diferite
• piesele vor fi marcate cu valori naturale consecutive, începând cu 1
• fiecare linie a matricei va fi afișată pe câte o linie a ecranului, elementele de pe o linie fiind separate prin câte un spațiu

Restricții și precizări

• 1 ≤ n ≤ 10
• orice aranjare corectă a pieselor se ia în considerare

Exemplu

Intrare

2

Ieșire

2 2 5 5
2 1 1 5
3 0 1 4
3 3 4 4

Explicație

Exemplul corespunde desenului de mai sus.

#include <bits/stdc++.h>

using namespace std;
int n, m , a[1025][1025];
int main()
{
    cin >> m;
    n = 1 ;
    for(int i = 1 ; i <= m  ; i ++) n *= 2;
    if(m == 1) a[1][1] = a[1][2] = a[2][1] = 1;
    else if(m == 2)
    {
        a[1][1] = a[1][2] = a[2][1] = 1;
        a[1][3] = a[1][4] = a[2][4] = 2;
        a[3][1] = a[4][1] = a[4][2] = 3;
        a[3][4] = a[4][3] = a[4][4] = 4;
        a[2][2] = a[2][3] = a[3][2] = 5;
    }
    else{
        int p = 0;
        int i , j;
        if(m % 2 == 1)
        {
            for(i = 1 ; i + 3 <= n ; i += 3)
                for(j = 1 ; j <= n ; j += 2)
                {
                    p ++;
                    a[i][j] = a[i][j+1] = a[i+1][j] = p;
                    p++;
                    a[i+1][j+1] = a[i+2][j] = a[i+2][j+1] = p;
                }
            i = n -1;
            for(j = 1; j <= n - 2; j += 3)
            {
                p ++;
                a[i][j] = a[i][j+1] = a[i+1][j] = p;
                p++;
                a[i+1][j+1] = a[i+1][j+2] = a[i][j+2] = p;
            }
            i = n - 1, j = n - 1;
            p ++;
            a[i][j] = a[i][j+1] = a[i+1][j] = p;
            }
            else
            {
                for(i = 1 ; i <= n - 4; i += 3)
                    for(j = 1 ; j <= n ; j += 2)
                    {
                        p ++;
                        a[i][j] = a[i][j+1] = a[i+1][j] = p;
                        p++;
                        a[i+1][j+1] = a[i+2][j] = a[i+2][j+1] = p;
                    }
                i = n - 3;
                for(j = 1; j <= n - 4; j += 3)
                {
                    p ++;
                    a[i][j] = a[i][j+1] = a[i+1][j] = p;
                    p++;
                    a[i+1][j+1] = a[i+1][j+2] = a[i][j+2] = p;
                }
                i = n - 1;
                for(j = 1; j <= n - 4; j += 3)
                {
                    p ++;
                    a[i][j] = a[i][j+1] = a[i+1][j] = p;
                    p++;
                    a[i+1][j+1] = a[i+1][j+2] = a[i][j+2] = p;
                }
                i = n - 3, j = n - 3;
                p ++;
                a[i][j] = a[i][j+1] = a[i+1][j] = p;
                p ++;
                a[i][j+2] = a[i][j+3] = a[i+1][j+3] = p;
                p ++;
                a[i+2][j] = a[i+3][j] = a[i+3][j+1] = p;
                p ++;
                a[i+2][j+3] = a[i+3][j+2] = a[i+3][j+3] = p;
                p ++;
                a[i+1][j+1] = a[i+1][j+2] = a[i+2][j+1] = p;
            }
        }
    for(int i =1; i <= n ; ++i)
    {
        for(int  j = 1 ; j <= n ; j ++)
            cout << a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}