avioane.cpp

# include <fstream>
using namespace std;
ifstream f("avioane.in");
ofstream g("avioane.out");
int i,j,K,maxx,n;
short a[20][20],sol[20][20];
struct elem
{
    short l,c;
}v[5][100];
void initializare ()
{
    int i;
    for (i=0; i<=n+1; ++i)
        a[0][i]=-2,a[n+1][i]=-2,a[i][0]=-2,a[i][n+1]=-2;
    //1
    v[1][1].l=1; v[1][1].c=3;
    v[1][2].l=2; v[1][2].c=1;
    v[1][3].l=2; v[1][3].c=2;
    v[1][4].l=2; v[1][4].c=3;
    v[1][5].l=2; v[1][5].c=4;
    v[1][6].l=2; v[1][6].c=5;
    v[1][7].l=3; v[1][7].c=3;
    v[1][8].l=4; v[1][8].c=2;
    v[1][9].l=4; v[1][9].c=3;
    v[1][10].l=4; v[1][10].c=4;
    v[1][11].l=5; v[1][11].c=3;
    //2
    v[2][1].l=3; v[2][1].c=1;
    v[2][2].l=5; v[2][2].c=2;
    v[2][3].l=4; v[2][3].c=2;
    v[2][4].l=3; v[2][4].c=2;
    v[2][5].l=2; v[2][5].c=2;
    v[2][6].l=1; v[2][6].c=2;
    v[2][7].l=3; v[2][7].c=3;
    v[2][8].l=4; v[2][8].c=4;
    v[2][9].l=3; v[2][9].c=4;
    v[2][10].l=2; v[2][10].c=4;
    v[2][11].l=3; v[2][11].c=5;
    //3
    v[3][1].l=5; v[3][1].c=3;
    v[3][2].l=4; v[3][2].c=1;
    v[3][3].l=4; v[3][3].c=2;
    v[3][4].l=4; v[3][4].c=3;
    v[3][5].l=4; v[3][5].c=4;
    v[3][6].l=4; v[3][6].c=5;
    v[3][7].l=3; v[3][7].c=3;
    v[3][8].l=2; v[3][8].c=2;
    v[3][9].l=2; v[3][9].c=3;
    v[3][10].l=2; v[3][10].c=4;
    v[3][11].l=1; v[3][11].c=3;
    //4
    v[4][1].l=3; v[4][1].c=1;
    v[4][2].l=4; v[4][2].c=2;
    v[4][3].l=3; v[4][3].c=2;
    v[4][4].l=2; v[4][4].c=2;
    v[4][5].l=3; v[4][5].c=3;
    v[4][6].l=5; v[4][6].c=4;
    v[4][7].l=4; v[4][7].c=4;
    v[4][8].l=3; v[4][8].c=4;
    v[4][9].l=2; v[4][9].c=4;
    v[4][10].l=1; v[4][10].c=4;
    v[4][11].l=3; v[4][11].c=5;
}
void back ()
{
    int i,j,q,ok,o;
    if (K>maxx)
    {
        maxx=K;
        for (i=1; i<=n; ++i)
            for (j=1; j<=n; ++j)
                sol[i][j]=a[i][j];
    }
    if (maxx<4)
    {
        for (i=1; i<=n-4; ++i)
        {
            for (j=1; j<=n-4; ++j)
            {
                for (q=1; q<=4; ++q)
                {
                    ok=1;
                    for (o=1; o<=11 && ok; ++o)
                        if (a[i+v[q][o].l-1][j+v[q][o].c-1]!=0) ok=0;

                    if (ok)
                    {
                        ++K;
                        for (o=1; o<=11; ++o)
                            a[i+v[q][o].l-1][j+v[q][o].c-1]=K;

                        back ();

                        --K;
                        for (o=1; o<=11; ++o)
                            a[i+v[q][o].l-1][j+v[q][o].c-1]=0;
                    }
                }
            }
        }
    }
}
int main ()
{
    f>>n;
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=n; ++j)
            f>>a[i][j];
    }
    initializare ();
    back ();

    g<<maxx<<"\n";
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=n; ++j)
            g<<sol[i][j]<<" ";
        g<<"\n";
    }

    return 0;
}