Cod sursă (job #766476)

#include <fstream>

#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3


using namespace std ;

ifstream cin ( "immortal.in" ) ;
ofstream cout ( "immortal.out" ) ;

typedef struct
{
   int l , c ;
} immortal;

typedef struct
{
  int l , c , dir ;
} moves ;

int d [ 5 ][ 2 ] = { { -1 , 0 } , { 0 , 1 } , { 1 , 0 } , { 0 , -1 } } ;
immortal imm [ 400 ] ;
moves sol [ 400 ] ;
int a [ 24 ][ 24 ] ;
int m , n , p ;

void solutions ( )
{
   for ( int i = p ; i > 1 ; i -- ) {
      cout << sol [ i ] .l - 1 << " " << sol [ i ] .c - 1<< " " << sol [ i ] .l + 2 * d [ sol [ i ] .dir ] [ 0 ] - 1 << " " << sol [ i ] .c + 2 * d [ sol [ i ] .dir ] [ 1 ] - 1 << " "  << "\n" ;
   }
}

void bkt ( int p )
{
   if ( p == 1) {
    solutions ( ) ;
    exit ( 0 ) ;
   }
   for ( int i = 0 ; i < p ; i ++ ) {
      int l = imm [ i ] .l , c = imm [ i ] .c ;
      for ( int dir = 0 ; dir < 5 ; dir ++ ) {
         int ln = l + d [ dir ] [ 0 ] ;
         int cn = c + d [ dir ] [ 1 ] ;
         int ln2 = ln + d [ dir ] [ 0 ] ;
         int cn2 = cn + d [ dir ] [ 1 ] ;
         if ( a [ ln ] [ cn ] != -1 && a [ ln2 ] [ cn2 ] == -1 ) {
            sol [ p ] = { l , c , dir } ;
            a [ l ] [ c ] = -1 ;
            imm[i] = { ln2, cn2 };
            a [ ln2 ] [ cn2 ] = i ;

            int x = a [ ln ] [ cn ] ;
            if ( x < p - 1 ) {
               imm [ x ] = imm [ p - 1 ] ;
               a [ imm [ x ] .l ] [ imm [ x ].c ] = x ;
            }

            a [ ln ] [ cn ] = -1 ;

            bkt ( p - 1 ) ;

            if ( x < p - 1 ) {
               imm [ p - 1] = imm [ x ] ;
               a [ imm [ p - 1 ] .l ] [ imm [ p - 1] .c ] = p - 1;
               imm [ x ] = { ln , cn } ;
            }

            a [ ln ] [cn ] = x ;
            a [ln2 ] [cn2 ] = -1 ;
            imm [ i ] = { l, c };
            a [ l ] [ c ] = i;
         }
      }
   }

}

int main ( )
{
   cin >> m >> n >> p ;

   for ( int i = 2 ; i <= m + 1 ; i ++ ) {
    a [ i ] [ 0 ] = a [ i ] [ 1 ] = a [ i ] [ n + 2 ] = a [ i ] [ n + 3 ] = p ;
   }
   for ( int i = 2 ; i <= n + 1 ; i ++ ) {
    a [ 0 ] [ i ] = a [ 1 ] [ i ] = a [ m + 2 ] [ i ] = a [ m + 3 ] [ i ] = p ;
   }
   for ( int i = 2 ; i < m + 2; i ++ ) {
    for ( int j = 2 ; j < n + 2 ; j++ ) {
      a [ i ] [ j ] = -1 ;
    }
   }

   for ( int i = 0 ; i < p ; i ++ ) {
      int l , c ;
      cin >> l >> c ;
      a [ l + 1 ] [ c + 1 ] = 1 ;
   }

   int counter = 0 ;
   for ( int i = 2 ; i < m + 2 ; i++ ) {
    for ( int j = 2 ; j < n + 2 ; j++ ) {
      if ( a [ i ] [ j ] != -1 ) {
        a [ i ] [ j ] = counter ;
        imm [ counter ++ ] = { i , j } ;
      }
    }
   }

   bkt ( p ) ;
   return 0 ;
}