《算法的乐趣》第六十三节

本节讨论华容道游戏中武将棋子的移动。移动棋子即在棋盘上清除原位置信息、在新位置写入信息，需要武将编号和移动方向两个参数。

本节讨论华容道游戏中武将棋子的移动。移动棋子即在棋盘上清除原位置信息、在新位置写入信息，需要武将编号和移动方向两个参数。判断能否移动时，因棋盘四周设有哨兵位，只需检查新位置是否为空或为当前武将自身（多格棋子移动时存在位置重叠，新位置为0或等于该武将编号均可移动），无需按方向分别处理。MoveHeroToNewState()函数在可移动时产生新棋局。根据规则，同一棋子连续移动算一步，因此移动成功后继续朝非原方向尝试移动，以便计算最小步数。

搜索算法采用广度优先策略：队列初始只有开局状态，每次取出一个棋局，若为结束状态则输出，否则枚举所有武将与方向的组合尝试移动，产生的新棋局若未重复则入队。SearchNewGameStates()用两重循环枚举武将和方向，TrySearchHeroNewState()尝试具体移动并按规则处理连续移动，重复棋局则忽略。

算法求得“横刀立马”开局最快81步解，另有“指挥若定”73步、“比翼横空”28步等解。广度优先搜索通常第一个输出即为最少步数解。用单独数组存放武将信息影响了速度，瓶颈在于复制棋局数据，可将武将信息压缩进board以优化。