携狗渡河问题

来源：百度知道 编辑：UC知道 时间：2024/05/10 20:05:44
一家五口人带着五只狗（家中每个成员各自拥有一只狗）去郊游。途中遇到一条河，他们租用了一艘小船，小船每次可载三个生物（人和狗）。可惜这五只狗性情古怪，它必须和自己的主人在一起才会安分。如果他的主人不在场，它绝对不能和其他人在一起（即使一会也不行）。当然，狗是可以和其他的狗在一起的。幸好丽莎的狗曾上过特技训练学校也会划船，另外四只却都不会。
请问怎样渡河？需要几趟？

ABCDE,abcde分别代表一家五口人和各自的五只狗,其中Aa代表丽莎及她的狗,()与[]内分别表示河的两岸状态,Aa→表示小船承载着Aa渡河及渡河方向:
初始状态(ABCDEabcde), []
1,(ABCDEde),abc→,[abc]
2,(ABCDEade),←a,[bc]
3,(ABCDEe),ad→,[abcd]
4,(ABCDEae),←a,[bcd]
5,(AEae),BCD→,[BCDbcd]
6,(ABEabe),←Bb,[CDcd]
7,(BEbe),Aa→,[ACDacd]
8,(BCEbce),←Cc,[ADad]
9,(bce),BCE→,[ABCDEad]
10,(abce),←a,[ABCDEd]
11,(ce),ab→,[ABCDEabd]
12,(ace),←a,[ABCDEbd]
13,(),ace→[ABCDEabcde]