Cod sursă (job #295611)

#include <fstream>

using namespace std;
ifstream f("immortal.in");
ofstream g("immortal.out");
int n,m,I,i,a[21][21],b[2][16],st[16][4],viu[16],nr,x,y,ok=1;
void afis()
{
    for(i=1;i<=I-1;i++)
    {
        g<<st[i][0]<<' '<<st[i][1]<<' '<<st[i][2]<<' '<<st[i][3]<<'\n';
    }
    ok=0;
    return;
}
void backt(int k)
{
    int x,y,pe;
    if(nr==1) afis();
    for(int i=1;i<=I&&ok;i++)
    {
        if(!viu[i]) continue;
        x=b[0][i];
        y=b[1][i];
        if(x+2<=n)
        {
            if(a[x+1][y]!=0&&a[x+2][y]==0)
            {
                st[k][0]=x;
                st[k][1]=y;
                st[k][2]=x+2;
                st[k][3]=y;
                pe=a[x+1][y];
                a[x+2][y]=i;
                a[x+1][y]=0;
                a[x][y]=0;
                b[0][i]+=2;
                viu[pe]=0;
                nr--;
                backt(k+1);
                nr++;
                viu[pe]=1;
                b[0][i]-=2;
                a[x+1][y]=pe;
                a[x+2][y]=0;
                a[x][y]=i;
            }
        }
        if(x-2>=1)
        {
            if(a[x-1][y]!=0&&a[x-2][y]==0)
            {
                st[k][0]=x;
                st[k][1]=y;
                st[k][2]=x-2;
                st[k][3]=y;
                pe=a[x-1][y];
                a[x][y]=0;
                a[x-2][y]=i;
                a[x-1][y]=0;
                b[0][i]-=2;
                viu[pe]=0;
                nr--;
                backt(k+1);
                nr++;
                viu[pe]=1;
                b[0][i]+=2;
                a[x-1][y]=pe;
                a[x-2][y]=0;
                a[x][y]=i;
            }
        }
        if(y+2<=m)
        {
            if(a[x][y+1]!=0&&a[x][y+2]==0)
            {
                st[k][0]=x;
                st[k][1]=y;
                st[k][2]=x;
                st[k][3]=y+2;
                pe=a[x][y+1];
                a[x][y]=0;
                a[x][y+2]=i;
                a[x][y+1]=0;
                b[1][i]+=2;
                viu[pe]=0;
                nr--;
                backt(k+1);
                nr++;
                viu[pe]=1;
                b[1][i]-=2;
                a[x][y+1]=pe;
                a[x][y+2]=0;
                a[x][y]=i;
            }
        }
        if(y-2>0)
        {
            if(a[x][y-1]!=0&&a[x][y-2]==0)
            {
                st[k][0]=x;
                st[k][1]=y;
                st[k][2]=x;
                st[k][3]=y-2;
                pe=a[x][y-1];
                a[x][y]=0;
                a[x][y-2]=i;
                a[x][y-1]=0;
                b[1][i]-=2;
                viu[pe]=0;
                nr--;
                backt(k+1);
                nr++;
                viu[pe]=1;
                b[1][i]+=2;
                a[x][y-1]=pe;
                a[x][y-2]=0;
                a[x][y]=i;
            }
        }
    }
}
int main()
{
    f>>n>>m>>I;
    for(i=1;i<=I;i++)
    {
        f>>x>>y;
        a[x][y]=i;
        b[0][i]=x;
        b[1][i]=y;
    }
    nr=I;
    for(i=1;i<=I;i++) viu[i]=1;
    backt(1);
    return 0;
}