Cod sursă (job #116121)

#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 memx[I][V][N];
short int nmemx[I];
int memy[I][V][N];
short int nmemy[I];
short int lastx[I];
short int lasty[I];
short int px[I][V];
short int ux[I][V];
short int py[I][V];
short int uy[I][V];
int actualx[N];
int actualy[N];

short int v[N][N];

short int n,m,nr;

mutare s[I];
short int ns;

bool gata;
bool merg;
int k,xk1,xk2,j1,j2,shift,yk1,yk2;

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=0;k1<n;k1++)
        printf("%d ",actualx[k1]);
    printf("\n\n");*/

    //verifica daca s-a mai ajuns aici
    xk1=0;
    while(actualx[xk1]==0)
        xk1++;
    xk2=n-1;
    while(actualx[xk2]==0)
        xk2--;
    yk1=0;
    while(actualy[yk1]==0)
        yk1++;
    yk2=m-1;
    while(actualy[yk2]==0)
        yk2--;

    for(i=0;i<nmemx[ns];i++)
    {
        j1=px[ns][i];
        j2=ux[ns][i];
        if(xk2-xk1!=j2-j1)
            continue;
        merg=1;
        j=j1; k=xk1;
        while(j<=j2 && k<=xk2 && merg)
        {
            if(memx[ns][i][j]!=actualx[k])
                merg=0;
            j++;
            k++;
        }
        if(merg)
        {
            //printf("AICI\n");
            return;
        }
        merg=1;
        j=j2; k=xk1;
        while(j>=j1 && k<=xk2 && merg)
        {
            if(memx[ns][i][j]!=actualx[k])
                merg=0;
            j--;
            k++;
        }
        if(merg)
        {
            //printf("AICI\n");
            return;
        }

        j1=py[ns][i];
        j2=uy[ns][i];
        if(yk2-yk1!=j2-j1)
            continue;
        merg=1;
        j=j1; k=yk1;
        while(j<=j2 && k<=yk2 && merg)
        {
            if(memy[ns][i][j]!=actualy[k])
                merg=0;
            j++;
            k++;
        }
        if(merg)
        {
            //printf("AICI\n");
            return;
        }
        merg=1;
        j=j2; k=yk1;
        while(j>=j1 && k<=yk2 && merg)
        {
            if(memy[ns][i][j]!=actualy[k])
                merg=0;
            j--;
            k++;
        }
        if(merg)
        {
            //printf("AICI\n");
            return;
        }
    }
    //retine actualx-ul
    px[ns][lastx[ns]]=xk1;
    ux[ns][lastx[ns]]=xk2;
    for(i=0;i<n;i++)
        memx[ns][lastx[ns]][i]=actualx[i];
    lastx[ns]++;
    if(lastx[ns]==V)
        lastx[ns]=0;
    if(nmemx[ns]<V-1)
        nmemx[ns]++;
    //retine actualy-ul
    py[ns][lasty[ns]]=yk1;
    uy[ns][lasty[ns]]=yk2;
    for(i=0;i<n;i++)
        memy[ns][lasty[ns]][i]=actualy[i];
    lasty[ns]++;
    if(lasty[ns]==V)
        lasty[ns]=0;
    if(nmemy[ns]<V-1)
        nmemy[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;
                actualx[L[i].x]-=1<<L[i].y;
                actualy[L[i].y]-=1<<L[i].x;
                v[L[i].x][L[i].y+j]=0;
                actualx[L[i].x]-=1<<(L[i].y+j);
                actualy[L[i].y+j]-=1<<L[i].x;
                v[L[i].x][L[i].y+j+j]=i;
                actualx[L[i].x]+= 1<<(L[i].y+j+j);
                actualy[L[i].y+j+j]+=1<<L[i].x;
                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;
                actualx[L[i].x]+= 1<<L[i].y;
                actualy[L[i].y]+= 1<<L[i].x;
                v[L[i].x][L[i].y+j]=poz;
                actualx[L[i].x]+= 1<<(L[i].y+j);
                actualy[L[i].y+j]+= 1<<L[i].x;
                v[L[i].x][L[i].y+j+j]=0;
                actualx[L[i].x]-= 1<<(L[i].y+j+j);
                actualy[L[i].y+j+j]-= 1<<L[i].x;
                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;
                actualx[L[i].x]-= 1<<L[i].y;
                actualy[L[i].y]-= 1<<L[i].x;
                v[L[i].x+j][L[i].y]=0;
                actualx[L[i].x+j]-= 1<<L[i].y;
                actualy[L[i].y]-= 1<<(L[i].x+j);
                v[L[i].x+j+j][L[i].y]=i;
                actualx[L[i].x+j+j]+= 1<<L[i].y;
                actualy[L[i].y]+= 1<<(L[i].x+j+j);
                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;
                actualx[L[i].x]+= 1<<L[i].y;
                actualy[L[i].y]+= 1<<L[i].x;
                v[L[i].x+j][L[i].y]=poz;
                actualx[L[i].x+j]+= 1<<L[i].y;
                actualy[L[i].y]+= 1<<(L[i].x+j);
                v[L[i].x+j+j][L[i].y]=0;
                actualx[L[i].x+j+j]-= 1<<L[i].y;
                actualy[L[i].y]-= 1<<(L[i].x+j+j);
                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;
        actualx[L[i].x]+= 1<<L[i].y;
        actualy[L[i].y]+= 1<<L[i].x;
    }
    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;
}