Cod sursă (job #764177)

#include <fstream>

using namespace std;

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

int cmat [ 23 ] [ 23 ] , ok ;

int backtrack ( int mat [ 23 ] [ 23 ] , int kill [ 6 ] , int afis [ 401 ] [ 5 ] , int lin , int col , int imm , int h ) {
   if ( ok == 1 )
      return 0;
   //cout << " \n" << ok << "\n" ;
   int i , j , ok  = 0 ;
   if ( h != 0 ) {
     // cout << h << " " << kill [ 4 ] << "\n" ;
      if ( kill [ 4 ] == 1 ) {
         mat [ kill [ 1 ] + 2 ] [ kill [ 2 ] ] = mat [ kill [ 1 ] ] [ kill [ 2 ] ] ;
         mat [ kill [ 1 ] ] [ kill [ 2 ] ] = mat [ kill [ 1 ] + 1 ] [ kill [ 2 ] ] = 0 ;
      }
      if ( kill [ 4 ] == 2 ) {
         mat [ kill [ 1 ] - 2 ] [ kill [ 2 ] ] = mat [ kill [ 1 ] ] [ kill [ 2 ] ] ;
         mat [ kill [ 1 ] ] [ kill [ 2 ] ] = mat [ kill [ 1 ] - 1 ] [ kill [ 2 ] ] = 0 ;
      }
      if ( kill [ 4 ] == 3 ) {
         mat [ kill [ 1 ] ] [ kill [ 2 ] + 2 ] = mat [ kill [ 1 ] ] [ kill [ 2 ] ] ;
         mat [ kill [ 1 ] ] [ kill [ 2 ] ] = mat [ kill [ 1 ] ] [ kill [ 2 ] + 1 ] = 0 ;
      }
      if ( kill [ 4 ] == 4 ) {
         mat [ kill [ 1 ] ] [ kill [ 2 ] - 2 ] = mat [ kill [ 1 ] ] [ kill [ 2 ] ] ;
         mat [ kill [ 1 ] ] [ kill [ 2 ] ] = mat [ kill [ 1 ] ] [ kill [ 2 ] - 1 ] = 0 ;
      }
   }
   if ( h != imm - 1 )
      for ( i = 1 ; i <= lin ; i ++ )
      {
         for ( j = 1 ; j <= col ; j ++ ) {
            if ( mat [ i ] [ j ] != 0 )
            {
             // cout << h << "\n" ;
               if ( mat [ i + 1 ] [ j ] > 0 && mat [ i + 2 ] [ j ] == 0 )
               {
                  afis [ h ] [ 1 ] = i ;
                  afis [ h ] [ 2 ] = j ;
                  afis [ h ] [ 3 ] = i + 2 ;
                  afis [ h ] [ 4 ] = j ;
                  kill [ 1 ] = i ;
                  kill [ 2 ] = j ;
                  kill [ 3 ] = mat [ i ] [ j ] ;
                  kill [ 4 ] = 1 ;
                  kill [ 5 ] = 3 ;
                  if (  backtrack ( mat , kill , afis , lin , col , imm , h + 1 ) == 1 )
                     return 1;
               }
               if ( mat [ i - 1 ] [ j ] > 0 && mat [ i - 2 ] [ j ] == 0 )
               {
                  afis [ h ] [ 1 ] = i ;
                  afis [ h ] [ 2 ] = j ;
                  afis [ h ] [ 3 ] = i - 2 ;
                  afis [ h ] [ 4 ] = j ;
                  kill [ 1 ] = i ;
                  kill [ 2 ] = j ;
                  kill [ 3 ] = mat [ i ] [ j ] ;
                  kill [ 4 ] = 2 ;
                  kill [ 5 ] = 3 ;
                  if (  backtrack ( mat , kill , afis , lin , col , imm , h + 1 ) == 1 )
                     return 1;
               }
               if ( mat [ i ] [ j + 1 ] > 0 && mat [ i ] [ j  + 2 ] == 0 )
               {
                  afis [ h ] [ 1 ] = i ;
                  afis [ h ] [ 2 ] = j ;
                  afis [ h ] [ 3 ] = i ;
                  afis [ h ] [ 4 ] = j + 2 ;
                  kill [ 1 ] = i ;
                  kill [ 2 ] = j ;
                  kill [ 3 ] = mat [ i ] [ j ] ;
                  kill [ 4 ] = 3 ;
                  kill [ 5 ] = 3 ;
                  if (  backtrack ( mat , kill , afis , lin , col , imm , h + 1 ) == 1 )
                     return 1;
               }
               if ( mat [ i ] [ j - 1 ] > 0 && mat [ i ] [ j - 2 ] == 0 )
               {
                  afis [ h ] [ 1 ] = i ;
                  afis [ h ] [ 2 ] = j ;
                  afis [ h ] [ 3 ] = i ;
                  afis [ h ] [ 4 ] = j - 2 ;
                  kill [ 1 ] = i ;
                  kill [ 2 ] = j ;
                  kill [ 3 ] = mat [ i ] [ j ] ;
                  kill [ 4 ] = 4 ;
                  kill [ 5 ] = 3 ;
                  if (  backtrack ( mat , kill , afis , lin , col , imm , h + 1 ) == 1 )
                     return 1;
               }
            }
         }
      }
   else
      {
         if ( ok == 0 ){
            ok = 1 ;//cout << h << "\n" ;
            for ( i = 0 ; i < h ; i ++ ) {
               cout << afis [ i ] [ 1 ] << " " << afis [ i ] [ 2 ] << " " << afis [ i ] [ 3 ] << " " << afis [ i ] [ 4 ] << "\n" ;
            }
            cout << "\n" ;
            h = 0 ;

            return 1 ;
         }
      }
      for ( i = 1 ; i <= lin ; i ++ )
      {
         for ( j = 1 ; j <= col ; j ++ ){
            mat [ i ] [ j ] = cmat [ i ] [ j ] ;
          }
      }
      return 0 ;
}

int main()
{
   int mat [ 23 ] [ 23 ] = {} ;
   int kill [ 6 ] = {} ;
   int afis [ 401 ] [ 5 ] ;
   int lin , col , imm ;
   int i , j , x , y ;

   cin >> lin >> col >> imm ;

   for ( i = 0 ; i <= lin ; i ++ )
         mat [ i ] [ 0 ] = mat [ i ] [ col + 1 ] = -1 ;
   for ( i = 0 ; i <= col ; i ++ )
         mat [ 0 ] [ i ] = mat [ lin + 1 ] [ i ] = -1 ;

   for ( i = 0 ; i < imm ; i ++ )
   {
      cin >> x >> y ;
      cmat [ x ] [ y ] = mat [ x ] [ y ] = 1 ;
   }
   kill [ 5 ] = 2395 ;


   return backtrack ( mat , kill , afis , lin , col , imm , 0 ) ;;
}