花容道是一款有益智力的游戏，游戏规则在此不再赘述。用电脑解华容道也是很好的编程练习。为了找到最少步数，求解程序一般采用广度优先搜索算法。华容道的一个常见开局如图1所示。广度优先搜索算法求解华容道的基本步骤：准备两个“全局变量”，队列Q和集合S，S代表“已知情况”.最初Q和S都是空的。将初始位置添加到队列Q的末尾并将初始位置设置为已知。当队列不为空时，从Q的leader处取当前位置curr。如果队列为空，则搜索结束，说明无解。如果curr是最终位置（曹操在门口，图2），则结束搜索，否则继续第5步。考虑curr中的每一个可移动的棋子，尝试上下左右移动得到一个newsituationnext，如果新情况未知（next?S），将其加入队列Q，置为known。此步骤可能会产生几种新情况。回到步骤2，其中“情况已知”并不要求每个棋子的位置都一样，而是要求棋子投影的形状一样（代码中用mask表示).例如图1中的张飞和赵云互换并没有产生新的情况，这意味着A规则可以大大缩小搜索空间。以上步骤很容易转换为C++代码，本文重点介绍第5步的实现//Step1std::unordered_setseen;std::dequequeue;//Step2Stateinitial;//填写首字母，省略。queue.push_back(initial);seen.insert(initial.toMask());//第三步while(!queue.empty()){constStatecurr=queue.front();queue.pop_front();//第一个Step4if(curr.isSolved())break;//Step5for(constState&next:curr.moves()){autoresult=seen.insert(next.toMask());if(result.second)queue.push_back(next);}}在上面的原始实现中，curr.move()将返回一个std::vector临时对象。一种节省成本的方法是准备一个std::vector“改变变量”，让curr.move()反复修改它，例如，将其更改为：//第1步，添加一个新的scratch变量std：:vectornextMoves;//第三步while(!queue.empty()){//...//第五步curr.fillMoves(&nextMoves);for(constState&next:nextMoves){/*略*/}}还有一种方法可以完全使用这个std::vector，将部分逻辑以lambda的形式传递给curr.move()。代码结构基本不变：//Step3while(!queue.empty()){//...//Step5curr.move([&seen,&queue](constState&next){autoresult=seen.insert(next.toMask());if(result.second)queue.push_back(next);});}这样，主程序的逻辑还是很清晰的，把不必要的开销降到最低。在我最早的实现中，curr.move()的参数是conststd::function&，但是我发现这里每次都会构造一个std::function对象，它会被分配一次内存，就显得一文不值了。因此，在目前的实现中，curr.move()是一个函数模板，这样可以自动匹配lambda参数（通常是struct对象），节省了std::function的内存分配。本文完整代码见https://github.com/chenshuo/recipes/…/puzzle/huarong.cc。需要用GCC4.7编译，解决图1的问题大约需要几十毫秒。练习：修改程序，打印每一步移动棋子的情况。原文链接：http://coolshell.cn/articles/10476.html
