题目
在八世纪的欧洲，一名男子若出现在非自己妻子的已婚妇女面前（即便只是短暂片刻），而该妇女的丈夫不在场，则被视为不合礼仪。
三对已婚夫妇要过一条河，唯一的交通工具是一只最多载两人的划艇。在不违反当时社交规范的前提下，他们能否将所有人安全送到对岸？如果可以，最少需要多少次过河（单程）？
分析
下面给出一个验证过的、最少的11次过河步骤表（丈夫和妻子分别记为 ABC/123）：
| 步骤 | 左岸（过后） | 船上（本次过河） | 右岸（过后） |
|---|---|---|---|
| 0 | A, B, C, 1, 2, 3 | (空) | |
| 1 | B, 2, C, 3 | A, 1 \(\rightarrow\) | A, 1 |
| 2 | A, B, 2, C, 3 | \(\leftarrow\) A | 1 |
| 3 | A, B, C | 2, 3 \(\rightarrow\) | 1, 2, 3 |
| 4 | A, B, C, 1 | \(\leftarrow\) 1 | 2, 3 |
| 5 | A, 1 | B, C \(\rightarrow\) | B, C, 2, 3 |
| 6 | A, 1, B, 2 | \(\leftarrow\) B, 2 | C, 3 |
| 7 | 1, 2 | A, B \(\rightarrow\) | A, B, C, 3 |
| 8 | 1, 2, 3 | \(\leftarrow\) 3 | A, B, C |
| 9 | 3 | 1, 2 \(\rightarrow\) | A, B, C, 1, 2 |
| 10 | 1, 3 | \(\leftarrow\) 1 | A, B, C, 2 |
| 11 | (空) | 1, 3 \(\rightarrow\) | A, B, C, 1, 2, 3 |
图示如下：
这个题解中，关键的地方有这么两步：
- 第3步，达成：所有男性在近岸（出发岸），所有女性在远岸（到达岸）
- 第8步，达成：所有女性在近岸，所有男性在远岸