Cod sursă (job #295604)

#include<cstdio>
using namespace std;
struct doi
{
    int x,y;
};
doi t[16],sol1[16],sol2[16],a[21][21];
int n,m,i,mort[16];
bool v[16],ok;
void bkt(int x)
{
    if(!ok)
    {
        for(int j=1;j<=i&&!ok;++j)
        {
            if(v[j])
            {
                if(!ok&&t[j].x>=3&&!a[t[j].x-2][t[j].y].x&&a[t[j].x-1][t[j].y].x)
                {
                    a[t[j].x-1][t[j].y].x=0;
                    v[a[t[j].x-1][t[j].y].y]=0;
                    mort[x]=a[t[j].x-1][t[j].y].y;
                    a[t[j].x][t[j].y].x=0;
                    a[t[j].x-2][t[j].y].x=1;
                    a[t[j].x-2][t[j].y].y=j;
                    sol1[x].x=t[j].x;
                    sol1[x].y=t[j].y;
                    sol2[x].x=t[j].x-2;
                    sol2[x].y=t[j].y;
                    t[j].x-=2;
                    if(x==i-1)
                        ok=1;
                    bkt(x+1);
                    t[j].x+=2;
                    a[t[j].x-2][t[j].y].x=0;
                    a[t[j].x][t[j].y].x=1;
                    a[t[j].x-1][t[j].y].y=mort[x];
                    v[a[t[j].x-1][t[j].y].y]=1;
                    a[t[j].x-1][t[j].y].x=1;
                    a[t[j].x][t[j].y].y=j;
                }
                if(!ok&&t[j].x<=n-2&&!a[t[j].x+2][t[j].y].x&&a[t[j].x+1][t[j].y].x)
                {
                    a[t[j].x+1][t[j].y].x=0;
                    v[a[t[j].x+1][t[j].y].y]=0;
                    mort[x]=a[t[j].x+1][t[j].y].y;
                    a[t[j].x][t[j].y].x=0;
                    a[t[j].x+2][t[j].y].x=1;
                    a[t[j].x+2][t[j].y].y=j;
                    sol1[x].x=t[j].x;
                    sol1[x].y=t[j].y;
                    sol2[x].x=t[j].x+2;
                    sol2[x].y=t[j].y;
                    t[j].x+=2;
                    if(x==i-1)
                        ok=1;
                    bkt(x+1);
                    t[j].x-=2;
                    a[t[j].x+2][t[j].y].x=0;
                    a[t[j].x][t[j].y].x=1;
                    a[t[j].x+1][t[j].y].y=mort[x];
                    v[a[t[j].x+1][t[j].y].y]=1;
                    a[t[j].x+1][t[j].y].x=1;
                    a[t[j].x][t[j].y].y=j;
                }
                if(!ok&&t[j].y>=3&&!a[t[j].x][t[j].y-2].x&&a[t[j].x][t[j].y-1].x)
                {
                    a[t[j].x][t[j].y-1].x=0;
                    v[a[t[j].x][t[j].y-1].y]=0;
                    mort[x]=a[t[j].x][t[j].y-1].y;
                    a[t[j].x][t[j].y].x=0;
                    a[t[j].x][t[j].y-2].x=1;
                    a[t[j].x][t[j].y-2].y=j;
                    sol1[x].x=t[j].x;
                    sol1[x].y=t[j].y;
                    sol2[x].x=t[j].x;
                    sol2[x].y=t[j].y-2;
                    t[j].y-=2;
                    if(x==i-1)
                        ok=1;
                    bkt(x+1);
                    t[j].y+=2;
                    a[t[j].x][t[j].y-2].x=0;
                    a[t[j].x][t[j].y].x=1;
                    a[t[j].x][t[j].y-1].y=mort[x];
                    v[a[t[j].x][t[j].y-1].y]=1;
                    a[t[j].x][t[j].y-1].x=1;
                    a[t[j].x][t[j].y].y=j;
                }
                if(!ok&&t[j].y<=m-2&&!a[t[j].x][t[j].y+2].x&&a[t[j].x][t[j].y+1].x)
                {
                    a[t[j].x][t[j].y+1].x=0;
                    v[a[t[j].x][t[j].y+1].y]=0;
                    mort[x]=a[t[j].x][t[j].y+1].y;
                    a[t[j].x][t[j].y].x=0;
                    a[t[j].x][t[j].y+2].x=1;
                    a[t[j].x][t[j].y+2].y=j;
                    sol1[x].x=t[j].x;
                    sol1[x].y=t[j].y;
                    sol2[x].x=t[j].x;
                    sol2[x].y=t[j].y+2;
                    t[j].y+=2;
                    if(x==i-1)
                        ok=1;
                    bkt(x+1);
                    t[j].y-=2;
                    a[t[j].x][t[j].y+2].x=0;
                    a[t[j].x][t[j].y].x=1;
                    a[t[j].x][t[j].y+1].y=mort[x];
                    v[a[t[j].x][t[j].y+1].y]=1;
                    a[t[j].x][t[j].y+1].x=1;
                    a[t[j].x][t[j].y].y=j;
                }
            }
        }
    }
}

int main()
{
    freopen("immortal.in","r",stdin);
    freopen("immortal.out","w",stdout);
    int j;
    scanf("%d%d%d",&n,&m,&i);
    for(j=1;j<=i;++j)
    {
        scanf("%d%d",&t[j].x,&t[j].y);
        a[t[j].x][t[j].y].x=1;
        a[t[j].x][t[j].y].y=j;
        v[j]=1;
    }
    bkt(1);
    for(j=1;j<i;++j)
    {
        printf("%d %d %d %d\n",sol1[j].x,sol1[j].y,sol2[j].x,sol2[j].y);
    }
    return 0;
}