华容道算法和使用广度搜索的一些单人游戏求解框架

最新无聊在玩华容道，结果玩的时候，有些关不知道怎么过，就自己想着写程序来求最小还原步数。经过一番搜索和思考，写出来下面的代码，其中借鉴了别人的红黑树的代码，还有就是使用广度搜索来求解的思想。

在写算法的过程中，突然想到还有其他的单人游戏也是可以用广度搜索来求解的，因此，就针对这类游戏写了一个框架，适用于状态数不会太变态的游戏，例如华容道，Unblock me(移动木块)之类的游戏。3阶以上的魔方就不能用这个框架，状态数太多，使用广度搜索的话内存完全不够用。

file: OnePlayerMap

#include <stdio.h>#include <sys/time.h>#include "OnePlayerGame.h"#include "HuaRongDaoMap.h"int main() {        {                HuaRongDaoMap state(12,"kcksbhbbhsbh");                printf("play game\n");                OnePlayerGame oneGame(&state);                struct timeval tpstart,tpend;                gettimeofday(&tpstart,NULL); //获取时间                oneGame.startFindSolution();                gettimeofday(&tpend,NULL);                printf("find solution time is %ld usecond\n",                                1000000 * (tpend.tv_sec - tpstart.tv_sec) + tpend.tv_usec-tpstart.tv_usec);                if (oneGame.hasSolution()) {                        oneGame.printSolution();                } else {                        printf("can't find solution.\n");                }                printf("OnePlayerMap allocate Node Count:%d\n", OnePlayerMap::count);        }        printf("OnePlayerMap Node Count after release:%d\n", OnePlayerMap::count);        return 0;}

这个框架只用参照HuaRongDaoMap.h(.cpp),重新写一个派生类，实现那几个函数，就可以很简单的运行了。