Cod sursă (job #295610)

#include <fstream>

using namespace std;

ifstream fin("immortal.in");
ofstream fout("immortal.out");

const int nmax= 20;
const int kmax= 15;
const int dx[]= {0, 0, 1, -1};
const int dy[]= {1, -1, 0, 0};

bool ok;
int n, m, k;

bool u[nmax+1][nmax+1];
int a[kmax+1], b[kmax+1], sol[kmax+1][4];

void backt( int x ) {
     if ( x==k-1 ) {
          ok= 1;
     } else if ( ok==0 ) {
          for ( int i= k; i>=1 && ok==0; --i ) {
               for ( int j= 0; j<4 && ok==0 && u[a[i]][b[i]]==1; ++j ) {
                    int a1= a[i]+dx[j], a2= a[i]+dx[j]*2, b1= b[i]+dy[j], b2= b[i]+dy[j]*2;
                    if ( a2>=1 && a2<=n && b2>=1 && b2<=m && u[a1][b1]==1 && u[a2][b2]==0 ) {
                         sol[x][0]= a[i], sol[x][1]= b[i], sol[x][2]= a2, sol[x][3]= b2;

                         u[a2][b2]= 1;
                         u[a1][b1]= u[a[i]][b[i]]= 0;
                         a[i]= a2, b[i]= b2;

                         backt(x+1);

                         a[i]= a2-dx[j]*2, b[i]= b2-dy[j]*2;
                         u[a1][b1]= u[a[i]][b[i]]= 1;
                         u[a2][b2]= 0;
                    }
               }
          }
     }
}

int main(  ) {
     fin>>n>>m>>k;
     for ( int i= 1; i<=k; ++i ) {
          fin>>a[i]>>b[i];
          u[a[i]][b[i]]= 1;
     }

     backt(0);

     for ( int i= 0; i<=k-2; ++i ) {
          fout<<sol[i][0]<<" "<<sol[i][1]<<" "<<sol[i][2]<<" "<<sol[i][3]<<"\n";
     }

     return 0;
}