// Filename: BFS_DFS_v2.hpp
#ifndef _BFS_DFS_HPP
#define _BFS_DFS_HPP

#include <list>
#include <vector>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/hashed_index.hpp>

using std::list;
using std::vector;
using boost::multi_index::multi_index_container;
using boost::multi_index::indexed_by;
using boost::multi_index::sequenced;
using boost::multi_index::ordered_unique;
using boost::multi_index::hashed_unique;
using boost::multi_index::identity;

struct NoCheckDup {};
struct OrderCheckDup {};
struct HashCheckDup {};

struct BFS {};
struct DFS {};

// 状态空间树搜索模板
// State：问题状态类，提供nextStep()和isTarget()成员函数
// SearchType：可选择BFS或DFS，缺省为BFS
// CheckDup：状态查重算法，可选择NoCheckDup,HashCheckDup,OrderCheckDup
template < class State, class SearchType = BFS, class CheckDup = NoCheckDup >
class StateSpaceTreeSearch
{
    // 当SearchType不为BFS和DFS时，出错
    template <class Cont, class S>
    struct SearchInserter
    {
    };

    // BFS算法对应的新结点插入策略
    template <class Cont>
    struct SearchInserter<Cont, BFS>
    {
    public:
        SearchInserter(Cont& c) : c_(c) {}
        typedef typename Cont::iterator iterator;
        typedef typename Cont::value_type value_type;
        void operator()(iterator it, const value_type& v) {
            c_.push_back(v);  //新结点插入到列表的末端，即未搜索的结点后
        }
    private:
        Cont& c_;
    };

    // DFS算法对应的新结点插入策略
    template <class Cont>
    struct SearchInserter<Cont, DFS>
    {
    public:
        SearchInserter(Cont& c) : c_(c) {}
        typedef typename Cont::iterator iterator;
        typedef typename Cont::value_type value_type;
        void operator()(iterator it, const value_type& v) {
            c_.insert(++it, v);  //新结点插入到未搜索的结点前
        }
    private:
        Cont& c_;
    };

    // 当CheckDup不为下面偏特化的三者之一时，出错
    template <class S, class C>
    struct Container
    {
    };

    // NoCheckDup策略采用list为容器
    template <class S>
    struct Container<S, NoCheckDup>
    {
        typedef list<S> Cont;
    };

    // OrderCheckDup策略采用multi_index_container为容器，有一个order唯一索引
    template <class S>
    struct Container<S, OrderCheckDup>
    {
        typedef multi_index_container< S,
            indexed_by< sequenced<>, ordered_unique< identity<S> > >
        > Cont;
    };

    // HashCheckDup策略采用multi_index_container为容器，有一个hash唯一索引
    template <class S>
    struct Container<S, HashCheckDup>
    {
        struct HashFcn
        {
            size_t operator()(const S& s) const { return s.hash(); }
        };
        typedef multi_index_container< S,
            indexed_by< sequenced<>, hashed_unique< identity<S>, HashFcn > >
        > Cont;
    };

public:
    typedef typename Container<State, CheckDup>::Cont Cont;
    typedef typename Cont::iterator iterator;
    typedef SearchInserter<Cont, SearchType> Inserter;

    template <class Func>
    int operator()(const State& initState, Func afterFindSolution) const
    // initState : 初始化状态，类State应提供成员函数nextStep()和isTarget()，
    //             nextStep()用vector<State>返回下一步可能的所有状态，
    //             isTarget()用于判断当前状态是否符合要求的答案；
    // afterFindSolution : 仿函式，在找到一个有效答案后调用之，它接受一个
    //                     const State&，并返回一个bool值，true表示停止搜索，
    //                     false表示继续搜索
    // return : 找到的答案数量
    {
        Cont states;
        Inserter inserter(states);
        states.push_back(initState);
        iterator head = states.begin();  //指向下个搜索的结点
        vector<State> nextStates;
        int n = 0;  //记录找到的解答数量
        bool stop = false;
        while (!stop && head != states.end())
        {
            State s = *head;  //搜索一个结点
            nextStates.clear();
            s.nextStep(nextStates);  //从搜索点生成下一层结点
            for (typename vector<State>::iterator i = nextStates.begin();
                 i != nextStates.end(); ++i)
            {
                if (i->isTarget())
                {  // 找到一个目标状态
                    ++n;
                    if (stop = afterFindSolution(*i))  //处理结果并决定是否停止
                    {
                        break;
                    }
                } else {  // 不是目标状态，插入树中，树所使用的容器类会自动查重
                    inserter(head, *i);
                }
            }
            ++head;  //指针移到下一个元素
        }
        return n;
    }
};

#endif

 相对应的新的推箱子程序如下：

// soko.cpp -- 推箱子主程序

#include <iostream>
#include "BFS_DFS_v2.hpp"
#include "SokoState_v1.h"

using namespace std;

bool printAnswer(const SokoState& s)
{
    s.printAnswer(cout);
    cout << endl;
    return true;
}

int main()
{
    SokoState initState;
    cin >> initState;
    cout << initState;
    StateSpaceTreeSearch<SokoState, BFS, OrderCheckDup> sokoSearch;
    int n = sokoSearch(initState, printAnswer);
    if (n == 0)
    {
        cout << "No answer." << endl;
    }
    return 0;
}