出个算法题，大家练练手【3个和尚和3个妖怪过河】

香川群子

离阳光更近 发表于 2020-12-3 22:08
扣扣501251105

啥事，不能请别人帮忙吗。

大宝佳琪

求助美女，多行多列唯一性提取怎样实现？共有3628800种情况

大宝佳琪

求助美女，帮解下这道题，谢谢！

paciguard

来晚了，看个头看个尾，还没有结帖吧？中间略过，先不参考别人的方法，容我想想

大宝佳琪

大宝佳琪

求助美女，多行多列唯一性提取？

gwjkkkkk

有趣，有空研究下。。。

MY→Email

原来，可以这么玩的呀。，感谢分享。

micch

翻回来再次看这个问题，初始状态到结束状态的变化，如果把一来一回算做一次变化，那么每次只能送一个过去，所以6个人/怪要过去，一个来回送一个过河，两岸的状态必然是：左边从6到0，右边从0到6，如果是求最短肯定就不考虑数量变少再变多的情况， 也就是只能数量左边减少右边增加，或者是在某一个来回数量相同无变化。

每发生一次来回，有三个状态要判断：左边剩余的人大等于怪，右边人大等于怪，船上必然是过去2个回来1个，并且状态不需要考虑。

如果双向判断，那么从3300开始左岸减少右岸增加，同时从0033也开始右岸减少左岸增加，（感觉其实是一回事），所以当出现左右岸状态相同时，就表示整个过程得到解了。那么找到这个中间过程，就只需要判断一半，将问题变为：  A → C      。 C的状态假设是过河一半，也就是  3300变为    ?(3)? = ?(3)?，左右岸各一半。  考虑到  人≥怪。   那么这个状态只能是 一边全是人，另一边全是怪。
所以找到从开始状态到把3个人或3个怪全送过河的中间状态。其实就得到结果了。

中间状态两种：3个人过河留下3个怪，3个怪过河留下3个人。     根据条件限制，人≥怪，那么怪全部过河的状态下船只能在怪的岸边，因为在人的岸边人过去几个都不满足限制。所以所有怪过河，并且船也过去。需要的次数就是怪的数量，因为一次只能过一个人或怪。         所以求出开始状态到全部怪在对岸的状态最短走法，就够了。

以上，仅仅为人类逻辑的一种猜测，不知道逻辑是否正确，也不会转化为代码逻辑进行验证

笑着...两年过去

zyuhai119 发表于 2018-9-28 16:26
返回也算一个步骤

思维模式共需7步 以左岸到右岸

不对，看题意，会发生这种情况：船上的妖看到对岸僧不比妖多，会下船伙同其他妖吃僧