前两天同事玩华容道，我突然想到写程序求解。前些天还与同学聊到人工智能和Web3.0，而我已经好久没写过算法复杂的程序了，于是心血来潮，折腾两天，弄出了个求解程序，与大家分享。

算法思想嘛，传统又经典的树加裁剪。最初我想偷懒用递归，但很快发现，树枝通过不同的路径可以发展到相同的状态。这些相同状态的树枝如果不除掉，不但浪费很多时间，更有可能导致死循环。没办法，老老实实写个树出来。节点是用数组存放的，节点中有父节点索引和级别，当然少不了曹操、关羽这帮人的信息。这些信息包括当前各人物所处位置和父节点经过什么样的移动得到本节点。

移动的判断，是我惯用的用二进制运算判断法。这一算法是我读大学时写俄罗斯方块摸索出来的，用起来很方便的，而且二进制运算效率又高。华容道与俄罗斯方块有一个共同特点，它们的移动的物体都可以看作是点阵型的，我们可以把背景想像成一个网格，格中有点就是1，无点就是0。如果我们再约定好一个顺序，这些0和1就组成二进制数了。所以，每种形状都可以通过此方法转换成一个数字。当它们发生移动时，可以用移位来计算新的数据。至于会不会重叠，就更好判断了，直接按位与运算，大于0就是有重叠。

好像没什么要说的了。循环吧，不死不休！只有用光节点数组的所有元素或解出答案时才退出。循环体内当然是一级一级的检查节点可以派生出哪些新节点，并把新一级节点添加进去。当然，不能漏掉是否解决的判断。

附上我的程序：点击下载