四對情侶過河問題 - 拼圖

※ 引述《hcldesmond (●^▽^●)》之銘言：
: 相信大家都聽過經典的狼羊草過河問題
: 以下的也很類似
: ---
: 有四對情侶要過河，河上有一艘小艇，每次最多只能載二人
: 河中央有一個小島，可讓部分人或所有人暫時站在那裡
: 四位男生互相妒忌，任何時候某位女生與其他男生待在一起時，她的男友必然在她身邊
: 四位女生都怕自己的男友會移情別戀，所以任何一位女生在小島或岸邊獨處時，
: 除了她的男友外，其他男生都不能獨自划艇，即使他的目的地不是該女生所在之處
: 問題是：每次小艇載人從一地往另一地算一步的話，如何用最少步數把所有人帶到對岸？
寫一下我推文裡寫的 19 步解好了

(以下有做法)











以 ABCD 表四男, abcd 表四女, []表地點, <>表要出發的人

1. [ABCD<ab>cd] [] []
2. [ABCDcd] [a<b>] []
3. [ABCD<bc>d] [a] []
4. [ABCDd] [ab<c>] []
5. [ABCD<cd>] [ab] []
6. [ABCD] [abc<d>] []
7. [<AB>CDd] [abc] []
8. [CDd] [abc] [A<B>]
9. [<BC>Dd] [abc] [A]
10. [Dd] [abc] [AB<C>]
11. [<CD>d] [abc] [AB]
12. [d] [abc] [ABC<D>]
13. [<Dd>] [abc] [ABC]
14. [] [abc] [ABCD<d>]
15. [] [<ab>cd] [ABCD]
16. [] [cd] [ABCDa<b>]
17. [] [<bc>d] [ABCDa]
18. [] [d] [ABCDab<c>]
19. [] [<cd>] [ABCDab]
End.[] [] [ABCDabcd]

想法很簡單

既然男生被"綁"在女友身邊

那一開始就先送女生出去

六步之後剩下 d 女 再把男生送過去

11.當中 D 男可以出發是因為所有男生都過去了

於是12.根據限制只有 D 男可以划回來

然後就是13.這一步把情形轉成7.之前的反向

所以就全部過去了

至於最少步數的討論

一個顯然的下限是在沒有任何限制時的步數 13 步

(六次兩個過去一個過來 最後兩個人過去 共 13 步)

而這裡顯然有不能到達13步的限制

因此接下來就是找有沒有其他14~18步的解了

--
'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513

--