图中状态记录左岸人数与船的位置，每条边表示一次满足条件的渡河。
三个警察和三个囚徒过河，凭直觉往返安排，很容易漏掉另一岸的约束。把它改写成状态图后，问题会清楚得多：什么叫一个局面，哪些动作能产生新局面，以及怎样知道找到的是最少渡河次数。
先把题目版本说清
这里讨论一个明确的经典变体：船最多坐两人，每次至少一人；任何人都能划船；两岸只要有警察，囚徒人数就不能超过警察。没有警察的一岸不受这条人数关系限制。目标是把六个人和船都送到右岸。
这些规则不能省略。若原题还规定某些人不会划船、船上也有额外约束，或者必须每位囚徒都有人看守，状态和可行动作都会改变。下面得到的路径只属于这里列出的版本，不把不同题面的答案混用。
用三个量表示一个局面
令状态为 (p，c，b)，p 和 c 分别表示左岸的警察数、囚徒数，b 表示船在哪边。右岸人数可以由总数三减去左岸人数得到，因此不必重复存储。起点为 (3，3，左)，终点为 (0，0，右)。
人数必须在零到三之间。左岸合法条件是 p 为零，或者 p 不少于 c；右岸同理，要么警察数为零，要么警察数不少于囚徒数。只检查船驶离的一岸，会把另一岸已经违规的局面错误放进搜索。
同样的人数配上不同船位置，是不同状态。船在右岸时不能直接从左岸挑两人出发，所以只用人数作为访问标记，会错误合并可行动作不同的局面。
枚举动作，再检查可行性
载客组合只有五类：一个警察、两个警察、一个囚徒、两个囚徒、各一个。从船所在岸出发，先判断那里有没有这些人，再更新左岸人数、翻转船位置，最后核对两岸是否合法。
动作本身可以枚举，但不能每一步都让船空着返回。题目要求船至少载一人，所以空船不是合法边。也不能为了不让局面“看起来倒退”而禁止人员返回；渡河问题本来就需要有人把船带回来。
例如先把两个囚徒送到右岸，左岸变成三个警察和一个囚徒，右岸没有警察，两岸都满足这里的条件。下一步再让一个囚徒带船返回，可以产生继续运人的新状态。回退人数不代表搜索无效。
为什么广度优先能给最短路径
这里每次渡河的代价都记为一。广度优先搜索先探索距离起点一步的状态，再探索两步的状态，依次向外扩展。第一次到达终点时，便已经得到最少渡河次数，不需要比较所有完整路线。
将状态入队时就标记已访问，能避免同一局面反复排队；同时保存它的前驱状态和载客动作，终点找到后沿前驱反向回溯，就能还原路线。只保存一个最短步数而不保存路径，无法检查每次载客是否满足规则。
该变体的一条最短路线需要十一趟。用“囚囚向右、囚向左、囚囚向右、囚向左、警警向右、警囚向左、警警向右、囚向左、囚囚向右、囚向左、囚囚向右”逐步核对，可得到合法终点；最短性则来自完整 BFS 层次搜索，而不是这条路线写得顺。
把证明和实现检查分开
状态正确性来自信息足够：人数和船位置能够决定下一步。转移正确性来自枚举全部允许载客组合并检查两岸。最优性来自每条边等代价及 BFS 的分层访问。三条依据分别成立，算法结论才完整。
如果改成不同载客人数耗时不同，最少趟数未必等于最短时间，此时要按边权选择合适的最短路算法。不要在成本模型改变之后，仍然沿用原来的 BFS 最优性说法。
面试里这道题真正可迁移的能力，是把叙事规则变成状态、不变量和转移。如果新增“只有警察会划船”，你会先删掉哪些动作，原来十一趟的结论还能直接使用吗？