Cod sursă (job #116220)

#include <stdio.h>

using namespace std;

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

struct lista{
    short int x,y,prev,next;
}L[T];
struct mutare{
    short int x,y,d;
}s[T];

int mem[T][V][N],actual[N];;
short int nmem[T],last[T],v[N][N];

short int n,m,nr,p=1,ns;

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

void bkt ()
{
    if(ok) return;
    if(ns==nr-1) {ok=1; return;}
    short int i=p,j,poz;

    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){
            return;
        }
    }
    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){
        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];
                s[ns].x=L[i].x; s[ns].y=L[i].y; s[ns].d=2+((j+1)>>1);
                ns++;

                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;

                bkt();
                if(ok) return;

                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];

                s[ns].x=L[i].x; s[ns].y=L[i].y; s[ns].d=(j+1)>>1;
                ns++;

                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;

                bkt();
                if(ok) return;

                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;
}