Найти возможные пути для шахматной фигуры «слон» от одной клетки до другой

/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <complex>
#include <iostream>
#include <map>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef int                     T_coord;
typedef std::complex<T_coord>   T_coords;
typedef std::string             T_str;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_bishop_cell
{
    static const char       VERT_MIN    = 'a';
    static const char       HORIZ_MIN   = '1';
    //-----------------------------------------------------------------------------------
    T_coords  coords_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    static const T_coord    COORD_MIN   = 1;
    static const T_coord    COORD_MAX   = 8;        
    //-----------------------------------------------------------------------------------
    T_bishop_cell
        (
            T_coord     horiz_coord     =   T_coord(),
            T_coord     vert_coord      =   T_coord()
        )
        :
        coords_
            (
                horiz_coord,
                vert_coord
            )
    {}
    //-----------------------------------------------------------------------------------
    bool  color() const
    {
        return      ( 
                            coords_.real() 
                        +   coords_.imag() 
                    ) 
                %   2   ==  0;
    }
    //-----------------------------------------------------------------------------------
    T_str  name() const
    {
        T_str  res_str;
        res_str.push_back( char(VERT_MIN   + coords_.imag() - COORD_MIN) );
        res_str.push_back( char(HORIZ_MIN  + coords_.real() - COORD_MIN) );
        return  res_str;
    }
    //-----------------------------------------------------------------------------------
    bool  successfully_assign( const T_str&  cell_name )
    {
        T_coord     horiz_coord     =   0;
        T_coord     vert_coord      =   0;
 
        bool  bool_res  =       cell_name.size() == 2
                            &&  get_horiz_coord
                                    (
                                        cell_name,
                                        horiz_coord
                                    )
 
                            &&  get_vert_coord
                                    (
                                        cell_name,
                                        vert_coord
                                    );
 
        if(bool_res)
        {
            coords_     =   T_coords
                                (
                                    horiz_coord,
                                    vert_coord
                                );
        }
 
        return  bool_res;    
    }
    //-----------------------------------------------------------------------------------
    bool  operator== (T_bishop_cell  cell)          const
    {
        return  coords_ == cell.coords_;
    }
    //-----------------------------------------------------------------------------------
    T_bishop_cell  operator- (T_bishop_cell  cell)  const
    {
        T_bishop_cell  res;
        res.coords_ = coords_ - cell.coords_;
        return  res;
    }
    //-----------------------------------------------------------------------------------
    bool  operator< (T_bishop_cell  cell)           const
    {
        return      std::make_pair
                        (
                            coords_.real(), 
                            coords_.imag()
                        )
 
                <   std::make_pair
                        (
                            cell.coords_.real(), 
                            cell.coords_.imag()
                        );
    }
    //-----------------------------------------------------------------------------------
    T_coord  abs_bishop_shift()                     const
    {
        return      abs( coords_.real() ) 
                ==  abs( coords_.imag() )
                        ? abs( coords_.real() )
                        : 0;
    }
    //-----------------------------------------------------------------------------------
    bool  bishop_shift_direction()                  const
    {
        return      coords_.real() 
                *   coords_.imag() > 0;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    static bool  get_horiz_coord
        (
            const T_str&    s,
            T_coord&        horiz_coord
        )
    {
        horiz_coord     =   s[1] - HORIZ_MIN + COORD_MIN;       
        return  coord_is_correct( horiz_coord );
    }
    //-----------------------------------------------------------------------------------
    static bool  get_vert_coord
        (
            const T_str&    s,
            T_coord&        vert_coord
        )
    {
        vert_coord      =   tolower(s[0]) - VERT_MIN + COORD_MIN;
        return  coord_is_correct( vert_coord );        
    }
    //-----------------------------------------------------------------------------------
    static bool  coord_is_correct(T_coord  coord)
    {
        return      COORD_MIN   <=  coord
                &&  coord       <=  COORD_MAX;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector     <T_bishop_cell>                         T_move;
typedef std::vector     <T_move>                                T_moves;
typedef std::map        <T_bishop_cell,    T_bishop_cell    >   T_adjacent_row;
typedef std::map        <T_bishop_cell,    T_adjacent_row   >   T_adjacent_matr;
/////////////////////////////////////////////////////////////////////////////////////////
void  input_cell_name
    (
        const T_str&    prompt,
        T_str&          cell_name
    )
{
    std::cout   <<  prompt;
    std::cin    >>  cell_name;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  make_adjacent_matr(T_adjacent_matr&   adjacent_matr)
{
    for(
        int  
        H   =   T_bishop_cell::COORD_MIN; 
        H   <=  T_bishop_cell::COORD_MAX; 
        ++H
       )
    {
        for(
            int  
            V   =   T_bishop_cell::COORD_MIN; 
            V   <=  T_bishop_cell::COORD_MAX; 
            ++V
           )
        {
            T_bishop_cell  start_cell(H, V);
 
            for(
                int  
                HH  =   T_bishop_cell::COORD_MIN; 
                HH  <=  T_bishop_cell::COORD_MAX; 
                ++HH
               )
            {
                for(
                    int  
                    VV  =   T_bishop_cell::COORD_MIN; 
                    VV  <=  T_bishop_cell::COORD_MAX; 
                    ++VV
                   )
                {
                    T_bishop_cell   finish_cell(HH, VV);
                    T_bishop_cell   shift_cell  =  finish_cell - start_cell;
 
                    if( shift_cell.abs_bishop_shift() != 0 )
                    {
                        adjacent_matr[start_cell][finish_cell] = shift_cell;
                    }
                }
            }
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_move( const T_move&  move )
{
    for(
        T_move::const_iterator  
        cell_it     =   move.begin();
        cell_it     !=  move.end();
        ++cell_it
       )
    {
        std::cout   <<  cell_it->name()
                    <<  '\t';
    }
    std::cout << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  make_move
    (
        const T_adjacent_matr&  adjacent_matr,
        T_bishop_cell&          start_cell,
        T_bishop_cell&          finish_cell,
        T_moves&                shortest_moves,
        int&                    min_move_len,
        bool&                   is_first_move,
        T_move                  cur_move,
        T_coord                 cur_move_len
    )
{    
    if( cur_move.empty() )
    {
        cur_move.push_back( start_cell );
        make_move
            (
                adjacent_matr,
                start_cell,
                finish_cell,
                shortest_moves,
                min_move_len,
                is_first_move,                
                cur_move,
                cur_move_len
            );
    }    
    else if( cur_move.back() == finish_cell )
    {
        //Проверяем ход на минимаьную длину.        
        if(
                is_first_move
            ||  cur_move_len    <   min_move_len
          )
        {
            is_first_move   =   false;
            min_move_len    =   cur_move_len;
            shortest_moves.clear        ();
            shortest_moves.push_back    (cur_move);
        }
        else if( cur_move_len == min_move_len )
        {
            shortest_moves.push_back(cur_move);
        }
    }
    else if(
                shortest_moves.empty()
            ||  cur_move_len < min_move_len 
           )
    {
        const T_adjacent_row&   cur_matr_row     
            =   adjacent_matr.find( cur_move.back() )->second;
 
        for(
            T_adjacent_row::const_iterator  
            cell_shift_it   =   cur_matr_row.begin  ();
            cell_shift_it   !=  cur_matr_row.end    ();
            ++cell_shift_it
           )
        {
            //Если клетки еще нет в ходе, и направление сдвига не совпадает с предыдущим, 
            //то добавляем ее в ход.
            bool    is_new_cell     =       std::find
                                                (
                                                    cur_move.begin  (),
                                                    cur_move.end    (),
                                                    cell_shift_it->first
                                                )
                                        ==  cur_move.end();
 
            if(!is_new_cell) continue;
 
            bool  is_new_shift_direction    
                =       cur_move.size() < 2
                    ||      cell_shift_it->second
                                .bishop_shift_direction()
                        !=  ( cur_move.back() - cur_move.rbegin()[1] )   
                                .bishop_shift_direction();
            
            if(!is_new_shift_direction) continue;
                       
            T_move  new_cur_move(cur_move);
            new_cur_move.push_back(cell_shift_it->first);
 
            make_move
                (
                    adjacent_matr,
                    start_cell,
                    finish_cell,
                    shortest_moves,
                    min_move_len,
                    is_first_move,                    
                    new_cur_move,
                    cur_move_len + cell_shift_it->second.abs_bishop_shift()
                );
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout   <<  "Введите координаты стартовой и финишной клеток для слона в виде d3 или f7:"
                <<  std::endl;
 
    T_str           start_cell_name;
    T_bishop_cell   start_cell;
    do
    {
        input_cell_name
            (
                "\tстартовая клетка:\t",
                start_cell_name
            );
    }while( 
            !start_cell.successfully_assign( start_cell_name )
          );
    
    std::cout   <<  std::endl;
 
    T_str           finish_cell_name;
    T_bishop_cell   finish_cell;
    do
    {
        input_cell_name
            (
                "\tфинишная клетка:\t",
                finish_cell_name
            );
 
    }while( 
                !finish_cell.successfully_assign( finish_cell_name )
            ||  finish_cell             ==  start_cell
            ||  finish_cell.color()     !=  start_cell.color()
          );   
 
    T_adjacent_matr  adjacent_matr;
    make_adjacent_matr( adjacent_matr );
    
    T_moves     shortest_moves;
    int         min_move_len    =   0;
    bool        is_first_move   =   true;
 
    make_move
        (
            adjacent_matr,
            start_cell,
            finish_cell,
            shortest_moves,
            min_move_len,
            is_first_move,
            T_move(),
            T_coord()
        );
 
    std::cout   << std::endl
                <<  "Кратчайшие пути слона из клетки "
                <<  start_cell.name()
                <<  " в клетку "
                << finish_cell.name()
                << ":"
                << std::endl;
 
    std::for_each
        (
            shortest_moves.begin(),
            shortest_moves.end(),
            print_move
        );
 
    std::cout   <<  std::endl;
}