Cod sursă (job #333353)

#include <stdio.h>
#include <string.h>

#define maxN 21
#define maxI 401
#define buffSize 131072

struct rec1
{
    int a,b,c,d;
}v[maxI];

struct rec2
{
    int x,y;
}nem[maxI];

int a[maxN][maxN];

int M,N,I;
int sol=0;

char buff[buffSize];
bool ok=true;
int ind=0;

inline void read(int &val)
{
    if(ok)
    {
        fread(buff,1,buffSize,stdin);
        ind=0;
        ok=false;
    }

    for(val=0;'0'<=buff[ind]&&buff[ind]<='9';)
    {
        val*=10;
        val+=(buff[ind]-'0');

        if(++ind==buffSize)
        {
            fread(buff,1,buffSize,stdin);
            ind=0;
        }
    }

    for(;('0'>buff[ind]||buff[ind]>'9')&&buff[ind]!='-';)
        if(++ind==buffSize)
        {
            fread(buff,1,buffSize,stdin);
            ind=0;
        }
}

inline void sim(int cnt)
{
    int x,y;
    if(cnt==1)
    {
        sol=1;
        return;
    }

    for(int i=1;i<=I;++i)
    {
        x=nem[i].x;
        y=nem[i].y;
        if(a[x][y]==i)
        {
            if(x>2&&a[x-1][y]&&a[x-2][y]==0)
            {
                a[x][y]=0;
                int aux=a[x-1][y];
                a[x-1][y]=0;
                a[x-2][y]=i;
                nem[i].x-=2;
                sim(cnt-1);
                if(sol)
                {
                    v[sol].a=x;
                    v[sol].b=y;
                    v[sol].c=x-2;
                    v[sol++].d=y;
                    return;
                }
                nem[i].x+=2;
                a[x-2][y]=0;
                a[x-1][y]=aux;
                a[x][y]=i;
            }

            if(x<M-1&&a[x+1][y]&&a[x+2][y]==0)
            {
                a[x][y]=0;
                int aux=a[x+1][y];
                a[x+1][y]=0;
                a[x+2][y]=i;
                nem[i].x+=2;
                sim(cnt-1);
                if(sol)
                {
                    v[sol].a=x;
                    v[sol].b=y;
                    v[sol].c=x+2;
                    v[sol++].d=y;
                    return;
                }
                nem[i].x-=2;
                a[x+2][y]=0;
                a[x+1][y]=aux;
                a[x][y]=i;
            }

            if(y>2&&a[x][y-1]&&a[x][y-2]==0)
            {
                a[x][y]=0;
                int aux=a[x][y-1];
                a[x][y-1]=0;
                a[x][y-2]=i;
                nem[i].y-=2;
                sim(cnt-1);
                if(sol)
                {
                    v[sol].a=x;
                    v[sol].b=y;
                    v[sol].c=x;
                    v[sol++].d=y-2;
                    return;
                }
                nem[i].y+=2;
                a[x][y-2]=0;
                a[x][y-1]=aux;
                a[x][y]=i;
            }

            if(y<N-1&&a[x][y+1]&&a[x][y+2]==0)
            {
                a[x][y]=0;
                int aux=a[x][y+1];
                a[x][y+1]=0;
                a[x][y+2]=i;
                nem[i].y+=2;
                sim(cnt-1);
                if(sol)
                {
                    v[sol].a=x;
                    v[sol].b=y;
                    v[sol].c=x;
                    v[sol++].d=y+2;
                    return;
                }
                nem[i].y-=2;
                a[x][y+2]=0;
                a[x][y+1]=aux;
                a[x][y]=i;
            }
        }
    }
}

int main()
{
    int x,y;

    memset(a,0,sizeof(a));
    memset(nem,0,sizeof(nem));

    freopen("immortal.in","r",stdin);

    read(M);
    read(N);
    read(I);
    for(int i=1;i<=I;++i)
    {
        read(x);
        read(y);
        a[x][y]=i;
        nem[i].x=x;
        nem[i].y=y;
    }

    sim(I);

    freopen("immortal.out","w",stdout);
    for(int i=sol-1;i>0;--i)
        printf("%d %d %d %d\n",v[i].a,v[i].b,v[i].c,v[i].d);

    return 0;
}