Cod sursă (job #116156)

#include <stdio.h>

using namespace std;

const short int I=17;
const short int N=21;
const int V=10;
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;

int mem[I][V][N];
short int nmem[I];
short int last[I];
int actual[N];

short int v[N][N];

short int n,m,nr;

mutare s[I];
short int ns;

bool gata;
bool merg;
int k,k1,k2,j1,j2,shift;

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

    /*for(k1=0;k1<n;k1++)
    {
        for(k2=0;k2<m;k2++)
            printf("%d ",v[k1][k2]);
        printf("\n");
    }
    for(k1=0;k1<n;k1++)
        printf("%d ",actual[k1]);
    printf("\n\n");*/

    //verifica daca s-a mai ajuns aici
    for(i=nmem[ns]-1;i>=0;i--)
    {
        merg=1;
        j=0;
        while(j<n && merg)
        {
            if(mem[ns][i][j]!=actual[j])
                merg=0;
            j++;
        }
        if(merg)
        {
            //printf("AICI\n");
            return;
        }
    }
    //retine actualul
    for(i=0;i<n;i++)
        mem[ns][last[ns]][i]=actual[i];
    last[ns]++;
    if(last[ns]==V)
        last[ns]=0;
    if(nmem[ns]<V-1)
        nmem[ns]++;

    i=p;
    while(i!=-1)
    {
        //verifica sus, jos, stanga, dreapta
        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;
                actual[L[i].x]-=1<<L[i].y;
                v[L[i].x][L[i].y+j]=0;
                actual[L[i].x]-=(int) 1<<(L[i].y+j);
                v[L[i].x][L[i].y+j+j]=i;
                actual[L[i].x]+=(int) 1<<(L[i].y+j+j);
                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;
                actual[L[i].x]+=(int) 1<<L[i].y;
                v[L[i].x][L[i].y+j]=poz;
                actual[L[i].x]+=(int) 1<<(L[i].y+j);
                v[L[i].x][L[i].y+j+j]=0;
                actual[L[i].x]-=(int) 1<<(L[i].y+j+j);
                ns--;
            }
        }
        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;
                actual[L[i].x]-=(int) 1<<L[i].y;
                v[L[i].x+j][L[i].y]=0;
                actual[L[i].x+j]-=(int) 1<<L[i].y;
                v[L[i].x+j+j][L[i].y]=i;
                actual[L[i].x+j+j]+=(int) 1<<L[i].y;
                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;
                actual[L[i].x]+=(int) 1<<L[i].y;
                v[L[i].x+j][L[i].y]=poz;
                actual[L[i].x+j]+=(int) 1<<L[i].y;
                v[L[i].x+j+j][L[i].y]=0;
                actual[L[i].x+j+j]-=(int) 1<<L[i].y;
                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;
        actual[L[i].x]+=(int) 1<<L[i].y;
    }
    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;
}