账号 自动登录 找回密码 密码 欢迎注册
 搜索

# [提问] 7人1狼过河问题

×

 一笔画问题

### 点评

2^7个状态，连通性问题吧  发表于 2024-8-16 12:21

 1狼和猎人过河，猎人回 2猎人和A仆人1过河，A仆人1回 3.A仆人1+2过河，A仆人1回 4.A+A仆人1过河，猎人+狼回 5.B+B仆人1过河，B仆人1回 6.B仆人1+2过河，B仆人1回 7.B仆人1+猎人过河，猎人回 8.猎人加狼过河

 只有猎人和剑客能够开船应该不行了，计算机穷举了一下 $./moving Total 136 valid states Not reachable Final best state:{ DogA1 DogA2 Hunter Wolf Boat }{ KnightA KnightB DogB1 DogB2 } Left to Right: { Hunter Wolf Boat }:state:{ DogA1 DogA2 }{ KnightA KnightB DogB1 DogB2 Hunter Wolf Boat } Right to Left: { KnightA Boat }:state:{ KnightA DogA1 DogA2 Boat }{ KnightB DogB1 DogB2 Hunter Wolf } Left to Right: { KnightA DogA2 Boat }:state:{ DogA1 }{ KnightA DogA2 KnightB DogB1 DogB2 Hunter Wolf Boat } Right to Left: { Hunter Wolf Boat }:state:{ DogA1 Hunter Wolf Boat }{ KnightA DogA2 KnightB DogB1 DogB2 } Left to Right: { DogA1 Hunter Boat }:state:{ Wolf }{ KnightA DogA1 DogA2 KnightB DogB1 DogB2 Hunter Boat } Right to Left: { Hunter Boat }:state:{ Hunter Wolf Boat }{ KnightA DogA1 DogA2 KnightB DogB1 DogB2 } Left to Right: { Hunter Wolf Boat }:state:{ }{ KnightA DogA1 DogA2 KnightB DogB1 DogB2 Hunter Wolf Boat } ### 点评 输出中把仆人换成狗了（仆人不会开船实在不是好的题目） 发表于 2024-8-17 07:53 毋因群疑而阻独见 毋任己意而废人言 毋私小惠而伤大体 毋借公论以快私情 回复 支持 反对 发表于 2024-8-17 07:56:33 | 显示全部楼层  只要把一只狗替换成仆人（能够开船），就可以了$ ./moving2 Total 136 valid states Left to Right: { Hunter Wolf Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 }{ Hunter Wolf Boat } Right to Left: { Hunter Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 Hunter Boat }{ Wolf } Left to Right: { ServantA1 Hunter Boat }:state:{ KnightA DogA2 KnightB DogB1 DogB2 }{ ServantA1 Hunter Wolf Boat } Right to Left: { ServantA1 Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 Boat }{ Hunter Wolf } Left to Right: { ServantA1 DogB2 Boat }:state:{ KnightA DogA2 KnightB DogB1 }{ ServantA1 DogB2 Hunter Wolf Boat } Right to Left: { ServantA1 Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 Boat }{ DogB2 Hunter Wolf } Left to Right: { KnightB DogB1 Boat }:state:{ KnightA ServantA1 DogA2 }{ KnightB DogB1 DogB2 Hunter Wolf Boat } Right to Left: { Hunter Wolf Boat }:state:{ KnightA ServantA1 DogA2 Hunter Wolf Boat }{ KnightB DogB1 DogB2 } Left to Right: { KnightA ServantA1 Boat }:state:{ DogA2 Hunter Wolf }{ KnightA ServantA1 KnightB DogB1 DogB2 Boat } Right to Left: { ServantA1 Boat }:state:{ ServantA1 DogA2 Hunter Wolf Boat }{ KnightA KnightB DogB1 DogB2 } Left to Right: { Hunter Wolf Boat }:state:{ ServantA1 DogA2 }{ KnightA KnightB DogB1 DogB2 Hunter Wolf Boat } Right to Left: { KnightA Boat }:state:{ KnightA ServantA1 DogA2 Boat }{ KnightB DogB1 DogB2 Hunter Wolf } Left to Right: { KnightA ServantA1 Boat }:state:{ DogA2 }{ KnightA ServantA1 KnightB DogB1 DogB2 Hunter Wolf Boat } Right to Left: { ServantA1 Boat }:state:{ ServantA1 DogA2 Boat }{ KnightA KnightB DogB1 DogB2 Hunter Wolf } Left to Right: { ServantA1 DogA2 Boat }:state:{ }{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 Hunter Wolf Boat }

 更好的方案是每个剑客带着一个仆人一条狗，但是高高在上的剑客不会划船 $./moving3 Total 136 valid states Left to Right: { Hunter Wolf Boat }:state:{ KnightA ServantA DogA KnightB ServantB DogB }{ Hunter Wolf Boat } Right to Left: { Hunter Boat }:state:{ KnightA ServantA DogA KnightB ServantB DogB Hunter Boat }{ Wolf } Left to Right: { ServantB Hunter Boat }:state:{ KnightA ServantA DogA KnightB DogB }{ ServantB Hunter Wolf Boat } Right to Left: { ServantB Boat }:state:{ KnightA ServantA DogA KnightB ServantB DogB Boat }{ Hunter Wolf } Left to Right: { ServantB DogB Boat }:state:{ KnightA ServantA DogA KnightB }{ ServantB DogB Hunter Wolf Boat } Right to Left: { ServantB Boat }:state:{ KnightA ServantA DogA KnightB ServantB Boat }{ DogB Hunter Wolf } Left to Right: { KnightB ServantB Boat }:state:{ KnightA ServantA DogA }{ KnightB ServantB DogB Hunter Wolf Boat } Right to Left: { Hunter Wolf Boat }:state:{ KnightA ServantA DogA Hunter Wolf Boat }{ KnightB ServantB DogB } Left to Right: { KnightA ServantA Boat }:state:{ DogA Hunter Wolf }{ KnightA ServantA KnightB ServantB DogB Boat } Right to Left: { ServantA Boat }:state:{ ServantA DogA Hunter Wolf Boat }{ KnightA KnightB ServantB DogB } Left to Right: { Hunter Wolf Boat }:state:{ ServantA DogA }{ KnightA KnightB ServantB DogB Hunter Wolf Boat } Right to Left: { ServantB Boat }:state:{ ServantA DogA ServantB Boat }{ KnightA KnightB DogB Hunter Wolf } Left to Right: { DogA ServantB Boat }:state:{ ServantA }{ KnightA DogA KnightB ServantB DogB Hunter Wolf Boat } Right to Left: { ServantB Boat }:state:{ ServantA ServantB Boat }{ KnightA DogA KnightB DogB Hunter Wolf } Left to Right: { ServantA ServantB Boat }:state:{ }{ KnightA ServantA DogA KnightB ServantB DogB Hunter Wolf Boat } 毋因群疑而阻独见 毋任己意而废人言 毋私小惠而伤大体 毋借公论以快私情 回复 支持 反对 楼主| 发表于 2024-8-17 14:55:42 | 显示全部楼层  mathe 发表于 2024-8-17 07:52 只有猎人和剑客能够开船应该不行了，计算机穷举了一下$ ./moving 当没有其他人在的时候，剑客A和B会决一死战同归于尽。这个条件是错的 不好意思，条件里面有一个写错了 当没有其他人在的时候，剑客A的仆人们和B的仆人们会决一死战同归于尽。

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2024-9-15 19:19 , Processed in 0.026229 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.