Cod sursă (job #114315)

#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 25
#define IMAX 30
#define get_min(a,b) ((a)<(b)?(a):(b))
#define get_max(a,b) ((a)>(b)?(a):(b))

using namespace std;

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

bool M[NMAX][NMAX];
pair < short , short > people[IMAX] , Sol[IMAX],PosStartPoint[IMAX], Sol_Second[IMAX];
short N , C , I , Answer , dx[]={ -1 , 1 , 0 , 0 } , dy[]= { 0 , 0 , -1 , 1 };
short dx1[] = { - 2 , 2 , 0 , 0 } , dy1[] = { 0 , 0 , -2 , 2} , Number_Peoples_Left ,k;
bool We_Have_Answer ;
int GotNeihgbor ( int x , int y )
{
    if ( M[x+1][y] or M[x-1][y] or M[x][y+1] or M[x][y-1] )
           return true;
    return false;
}
bool OutOfField ( int x  , int y )
{
    if ( x < 1 or x > N or y < 1 or y > C )
        return true ;
    return false ;
}

int Find( int x , int y )
{
    for ( int i = 1 ; i <= k ; ++i )
        if ( PosStartPoint[i].first == x and PosStartPoint[i].second == y )
            return i ;
    return 0;
}
void Backtracking ( int Answer )
{
    if ( Number_Peoples_Left == 1 )
    {
        We_Have_Answer = 1 ;
        return ;
    }
    bool da;
    int xnou , ynou , i , future_pos_X , future_pos_Y , j , x , y ;
    for ( j = 1 ; j <= I; ++j )
    {
        x = PosStartPoint[j].first;
        y = PosStartPoint[j].second;
        if ( M[x][y] )
    for ( i  = 0 ; i < 4  && We_Have_Answer == 0; ++i )
    {
        xnou = x + dx[i] ;
        future_pos_X = x + dx1[i];
        ynou = y + dy[i] ;
        future_pos_Y = y + dy1[i];
        if ( OutOfField( xnou  , ynou ) or OutOfField(future_pos_X , future_pos_Y) )
             continue;
        if ( M[xnou][ynou] == 1 and M[future_pos_X][future_pos_Y] == 0 )
        {
        --Number_Peoples_Left;
        Sol[Answer].first = x ;
        Sol[Answer].second = y ;
        Sol_Second[Answer].first = future_pos_X ;
        Sol_Second[Answer].second = future_pos_Y;
        M[x][y] = M[xnou][ynou]  =  0;
        M[future_pos_X][future_pos_Y]  = 1;
        PosStartPoint[j].first = future_pos_X;
        PosStartPoint[j].second = future_pos_Y;
        Backtracking( Answer + 1 ) ;
        M[x][y] = M[xnou][ynou] = 1 ;
        M[future_pos_X][future_pos_Y] = 0 ;
        PosStartPoint[j].first = x ;
        PosStartPoint[j].second = y;
        if ( We_Have_Answer == 1 )
            return ;
        ++Number_Peoples_Left;
        }
    }
    }


}
int main ( void )
{
    int i , j ;
    in >> N >> C >> I ;
    M[0][0] = 1 ;
    for ( i = 1 ; i <= I ; ++i )
        in >> people[i].first >> people[i].second ,
            M[people[i].first][people[i].second] = 1,
                PosStartPoint[i] = people[i];
    Number_Peoples_Left = I;
    Backtracking ( 1 );
    for ( i = 1 ; i < I ; ++i )
        out << Sol[i].first << " " << Sol[i].second << " " << Sol_Second[i].first << " " << Sol_Second[i].second << "\n";
    in.close();
    out.close();
    return 0;
}