Миссионеры и людоеды

/////////////////////////////////////////////////////////////////////////////////////////
// Миссионеры и людоеды.
// Три миссионера и три людоеда находятся по одну сторону реки, через которую они хотят 
// переправиться. В их распоряжении имеется лодка, которая может выдержать вес только 
// двух человек. Кроме того, если в какой-то момент число людоедов станет больше числа 
// миссионеров, миссионеры будут съедены независимо от того, на каком берегу реки это 
// случится.
// Нужно решить задачу рекурсивным методом
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
struct T_missionaries_and_cannibals_state
{
    //-----------------------------------------------------------------------------------
    struct  T_go_arg
    {
        bool  forward_;
        int   missionaries_;
        int   cannibals_; 
        //-------------------------------------------------------------------------------
        T_go_arg
            (
                bool  forward,
                int   missionaries,
                int   cannibals
            )
            : forward_       (forward),
              missionaries_  (missionaries),
              cannibals_     (cannibals)
        {}
    };
    //-----------------------------------------------------------------------------------
    typedef std::vector<T_go_arg>  T_go_args;
    //-----------------------------------------------------------------------------------
    int   missionaries_here_;
    int   cannibals_here_;
    int   missionaries_there_;
    int   cannibals_there_;
    bool  boat_is_here_;    
    //-----------------------------------------------------------------------------------
    T_missionaries_and_cannibals_state
        (
            int   missionaries_here,
            int   cannibals_here,
            int   missionaries_there,
            int   cannibals_there,
            bool  boat_is_here
        )
        : missionaries_here_   (missionaries_here),
          cannibals_here_      (cannibals_here),
          missionaries_there_  (missionaries_there),
          cannibals_there_     (cannibals_there),
          boat_is_here_        (boat_is_here)
    {}
    //-----------------------------------------------------------------------------------
    bool  operator== (const T_missionaries_and_cannibals_state&  state) const
    {
        return    cannibals_here_      == state.cannibals_here_
               && cannibals_there_     == state.cannibals_there_
               && missionaries_here_   == state.missionaries_here_
               && missionaries_there_  == state.missionaries_there_
               && boat_is_here_        == state.boat_is_here_;
    }
    //-----------------------------------------------------------------------------------
    operator bool() const
    {
        return    cannibals_here_       >= 0               
               && cannibals_there_      >= 0
               && (missionaries_here_   == 0 || missionaries_here_   >= cannibals_here_ )
               && (missionaries_there_  == 0 || missionaries_there_  >= cannibals_there_);
    }
    //-----------------------------------------------------------------------------------
    bool  go(const T_go_arg&  go_arg)
    {
        int  missionaries  = go_arg.missionaries_;
        int  cannibals     = go_arg.cannibals_;
        if(go_arg.forward_)
        { 
            if(!boat_is_here_) return  false;    
        }
        else
        {
            if(boat_is_here_) return  false;
            missionaries  *= -1;
            cannibals     *= -1;
        }
        boat_is_here_        = !boat_is_here_;
        missionaries_here_   -= missionaries;
        missionaries_there_  += missionaries;
 
        cannibals_here_      -= cannibals;
        cannibals_there_     += cannibals;
        return  *this;
    }
    //-----------------------------------------------------------------------------------    
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<T_missionaries_and_cannibals_state>  T_history;
/////////////////////////////////////////////////////////////////////////////////////////
void  go_missionaries_and_cannibals
    (
        T_history                                             history,
        const T_missionaries_and_cannibals_state&             finish_state,
        const T_missionaries_and_cannibals_state::T_go_args&  go_args
    )
{
    if(history.back() == finish_state)
    {
        std::cout << "м.зд"
                  << "\t"
                  << "л.зд"
                  << "\t"
                  << "м.там"
                  << "\t"
                  << "л.там"
                  << std::endl;
                  
        for(T_history::const_iterator  state_it = history.begin();
            state_it != history.end(); ++state_it)
        {
            std::cout << state_it->missionaries_here_
                      << "\t"
                      << state_it->cannibals_here_
                      << "\t"
                      << state_it->missionaries_there_
                      << "\t"
                      << state_it->cannibals_there_
                      << std::endl
                      << std::endl;
        }
        return;
    }
            
    if(
        history.size() > 1
        &&
        std::find
            (
                history.rbegin() + 1,
                history.rend(),
                history.back()
            ) 
            != history.rend()
      )
    {
        return;
    }
 
    for(T_missionaries_and_cannibals_state::T_go_args::const_iterator  arg_it = go_args.begin();
        arg_it != go_args.end(); ++arg_it)
    {
        T_missionaries_and_cannibals_state  next_state = history.back();
        if( !next_state.go(*arg_it) ) continue;
        T_history  new_history = history;    
        new_history.push_back(next_state);
        go_missionaries_and_cannibals
            (
                new_history, 
                finish_state, 
                go_args
            );    
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_missionaries_and_cannibals_state::T_go_args  go_args;
    for(int  forward = 0; forward <= 1; ++forward)
    {
        for(int  missionaries = 0; missionaries <= 2; ++missionaries)
        {
            for(int  cannibals = 0; cannibals <= 2; ++cannibals)
            {
                int  sum = missionaries + cannibals;
                if(   sum < 1
                   || sum > 2 )
                {
                    continue;
                }
                go_args.push_back
                    ( 
                        T_missionaries_and_cannibals_state::T_go_arg
                            (
                                forward == 0, 
                                missionaries, 
                                cannibals
                            ) 
                    );
            }
        }
    }
 
    T_missionaries_and_cannibals_state  start_state   (3, 3, 0, 0, true  );
    T_missionaries_and_cannibals_state  finish_state  (0, 0, 3, 3, false );
    T_history                           history       (1, start_state);
    go_missionaries_and_cannibals
        (
            history, 
            finish_state, 
            go_args
        );    
}