Cod sursă (job #114477)

#include <fstream>
#include <cstdlib>
#define Smerenie 20
#define Dragoste 15
#define Nadejde 4
#define Trufie -1

using namespace std ;

typedef struct {
        short l , c ;
}       NonDead ;
typedef struct {
        short l , c , dir ;
}       Solution;

NonDead Immo[ Dragoste ] ;
Solution Sol[ Dragoste ] ;

short nl , nc , nondead ;
short a[ Smerenie + 4 ][ Smerenie + 4 ] ;
short Move[ Nadejde ][ 2 ] = { { -1 , 0 } , { 0 , 1 } , { 1 , 0 } , { 0 , -1 } } ;

ofstream fout ( "immortal.out" ) ;

void PrintSolution( )
{
    short i ;

    for( i = nondead ; i > 1 ; i -- )
       {
          fout<<Sol[ i ].l - 1 <<" ";
          fout<<Sol[ i ].c - 1 <<" ";
          fout<<Sol[ i ].l + ( Move[ Sol[ i ].dir ][ 0 ] <<1 ) - 1 <<" ";
          fout<<Sol[ i ].c + ( Move[ Sol[ i ].dir ][ 1 ] <<1 ) - 1 <<" ";
          fout<<"\n";
       }
    ///fout<<"Dumnezeule milostiv fii mie pacatosului ";
    fout.close( ) ;

}

void Backtracking( short k )
{

    short i ;
    short dirr ;
    short l1 ;
    short l2 ;
    short c1 ;
    short c2 ;
    short dead ;

    if( k == 1 )
      {
        PrintSolution( ) ;
        exit( 0 ) ;
      }
    for( i = 0 ; i < k ; i ++ )
       {
         for( dirr = 0 ; dirr < Nadejde ; dirr ++ )
            {
              l1 = Immo[ i ].l + Move[ dirr ][ 0 ] ;
              c1 = Immo[ i ].c + Move[ dirr ][ 1 ] ;
              l2 = l1 + Move[ dirr ][ 0 ] ;
              c2 = c1 + Move[ dirr ][ 1 ] ;

              if( a[ l1 ][ c1 ] != Trufie && a[ l2 ][ c2 ] == Trufie )
                {
                  Sol[ k ] = { Immo[ i ].l , Immo[ i ].c , dirr } ;
                  a[ Immo[ i ].l ][ Immo[ i ].c ] = Trufie ;
                  Immo[ i ].l = l2 ;
                  Immo[ i ].c = c2 ;
                  a[ l2 ][ c2 ] = i ;

                  dead = a[ l1 ][ c1 ] ;
                  a[ l1 ][ c1 ] = Trufie ;

                  if( dead != k - 1 )
                    {
                      Immo[ dead ] = Immo[ k - 1 ] ;
                      a[ Immo[ dead ].l ][ Immo[ dead ].c ] = dead ;
                    }

                  Backtracking( k - 1 ) ;

                  if( dead != k - 1 )
                    {
                      a[ Immo[ dead ].l ][ Immo[ dead ].c ] = k - 1 ;
                      Immo[ dead ] = { l1 , c1 } ;
                    }
                  a[ l1 ][ c1 ] = dead ;
                  a[ l2 ][ c2 ] = Trufie ;
                  Immo[ i ].l = Immo[ i ].l - ( Move[ dirr ][ 0 ]<<1 ) ;
                  Immo[ i ].c = Immo[ i ].c - ( Move[ dirr ][ 1 ]<<1 ) ;
                  a[ Immo[ i ].l ][ Immo[ i ].c ] = i ;
                }
            }
       }
}

int main( )
{

    ifstream fin( "immortal.in" ) ;

    short i ;
    short j ;

    fin>> nl ;
    fin>> nc ;
    fin>> nondead ;

    for( i = 2 ; i <= nl + 2 ; i ++ )
       {
           a[ i ][ 0 ] = a[ i ][ 1 ] = a[ i ][ nc + 1 ] = a[ i ][ nc + 2 ] = nondead ;
       }
    for( i = 2 ; i <= nc + 2 ; i ++ )
       {
           a[ 0 ][ i ] = a[ 1 ][ i ] = a[ nl + 1 ][ i ] = a[ nl + 2 ][ i ] = nondead ;
       }
    for( i = 2 ; i <= nl + 1 ; i ++ )
       {
         for( j = 2 ; j <= nc + 1 ; j ++ )
            {
              a[ i ][ j ] = Trufie ;
            }
       }
     for( i = 0 ; i < nondead ; i ++ )
        {
          fin>>Immo[ i ].l ;
          Immo[ i ].l ++ ;
          fin>>Immo[ i ].c ;
          Immo[ i ].c ++ ;
          a[ Immo[ i ].l ][ Immo[ i ].c ] = i ;
        }


     Backtracking( nondead ) ;

     fin.close( ) ;

     return 0 ;
}