Cod sursă (job #115729)

#include <stdio.h>

using namespace std;

const short int I=17;
const short int N=21;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};

struct lista
{
    short int x;
    short int y;
    short int prev;
    short int next;
};

struct mutare
{
    short int x;
    short int y;
    short int d;
};

lista L[I];
short int p=1;

short int v[N][N];
short int n,m,nr;

mutare s[I];
short int ns;

bool gata;

void bkt ()
{
    //printf("ns=%d\n",ns);
    if(gata) return;
    if(ns==nr-1) {gata=1; return;}
    short int i=p,j,poz;

    /*short int k1,k2;
    for(k1=0;k1<n;k1++)
    {
        for(k2=0;k2<m;k2++)
            printf("%d ",v[k1][k2]);
        printf("\n");
    }
    for(k1=p;k1!=-1;k1=L[k1].next)
        printf("%d pe %d %d\n",k1,L[k1].x,L[k1].y);
    printf("\n");*/

    while(i!=-1)
    {
        //verifica sus, jos, stanga, dreapta
        for(j=-1;j<=1;j+=2)
        {
            if(L[i].x+j+j>=0 && L[i].x+j+j<n && v[L[i].x+j+j][L[i].y]==0 && v[L[i].x+j][L[i].y])
            {
                poz=v[L[i].x+j][L[i].y];
                //retine mutarea
                s[ns].x=L[i].x; s[ns].y=L[i].y; s[ns].d=(j+1)>>1;
                ns++;

                //omoara inamicul de pe poz
                //printf("poz=%d\n",poz);
                if(poz==p) p=L[poz].next;
                else
                {
                    L[L[poz].prev].next=L[poz].next;
                    L[L[poz].next].prev=L[poz].prev;
                }
                v[L[i].x][L[i].y]=0;
                v[L[i].x+j][L[i].y]=0;
                v[L[i].x+j+j][L[i].y]=i;
                L[i].x+=j+j;

                //apeleaza bkt
                bkt();
                if(gata) return;

                //refa situatia initiala
                L[i].x-=j+j;
                if(p==L[poz].next)  p=poz;
                else L[L[poz].prev].next=poz;
                L[L[poz].next].prev=poz;
                v[L[i].x][L[i].y]=i;
                v[L[i].x+j][L[i].y]=poz;
                v[L[i].x+j+j][L[i].y]=0;
                ns--;
            }
        }
        for(j=-1;j<=1;j+=2)
        {
            if(L[i].y+j+j>=0 && L[i].y+j+j<m && v[L[i].x][L[i].y+j+j]==0 && v[L[i].x][L[i].y+j])
            {
                poz=v[L[i].x][L[i].y+j];
                //retine mutarea
                s[ns].x=L[i].x; s[ns].y=L[i].y; s[ns].d=2+((j+1)>>1);
                ns++;

                //omoara inamicul de pe poz
                //printf("poz=%d\n",poz);
                if(poz==p) p=L[poz].next;
                else
                {
                    L[L[poz].prev].next=L[poz].next;
                    L[L[poz].next].prev=L[poz].prev;
                }
                v[L[i].x][L[i].y]=0;
                v[L[i].x][L[i].y+j]=0;
                v[L[i].x][L[i].y+j+j]=i;
                L[i].y+=j+j;

                //apeleaza bkt
                bkt();
                if(gata) return;

                //refa situatia initiala
                L[i].y-=j+j;
                if(p==L[poz].next)  p=poz;
                else L[L[poz].prev].next=poz;
                L[L[poz].next].prev=poz;
                v[L[i].x][L[i].y]=i;
                v[L[i].x][L[i].y+j]=poz;
                v[L[i].x][L[i].y+j+j]=0;
                ns--;
            }
        }
        i=L[i].next;
    }
}

int main()
{
    FILE *in,*out;
    in=fopen("immortal.in","r");
    out=fopen("immortal.out","w");

    short int i,x,y;
    fscanf(in,"%hd%hd%hd",&n,&m,&nr);
    for(i=1;i<=nr;i++)
    {
        fscanf(in,"%hd%hd",&x,&y);
        x--; y--;
        v[x][y]=i;
        L[i].x=x;
        L[i].y=y;
        L[i].next=i+1;
        L[i].prev=i-1;
    }
    L[nr].next=-1;

    bkt();

    for(i=0;i<ns;i++)
        fprintf(out,"%hd %hd %hd %hd\n",s[i].x+1,s[i].y+1,s[i].x+1+2*dx[s[i].d],s[i].y+1+2*dy[s[i].d]);

    return 0;
}