注册 登录
编程论坛 数据结构与算法

八人过河问题

小码农 发布于 2014-12-25 01:27, 1838 次点击
前几天看到了一个有趣的问题,大家思考下,就不给分了。
背景跳过。有八个人要过河,分别是爸爸,妈妈,姐姐,妹妹,哥哥,弟弟,一家六口,外加一名警察和一名逃犯。
只有一艘小船,每次可坐两人,但只有爸爸,妈妈,与警察可撑船。
条件如下:1、警察与逃犯不能分开,否则逃犯会伤害别人或逃走。
2、爸爸照顾姐妹俩时,会责备她们。
3、妈妈照顾兄弟二人时,会责备他们。
4 回复
#2
小码农2014-12-28 15:26
我要写我的做法了:
1、爸爸妈妈坐船过去
2、爸爸坐船回来
3、爸爸带哥哥过去
4、爸爸妈妈坐船回来
5、爸爸带弟弟过去
6、爸爸坐船回来
7、爸爸妈妈坐船过去
8、妈妈坐船回来
9、警察与逃犯坐船过去
10、爸爸坐船回来
11、爸爸妈妈坐船过去
12、妈妈坐船回来
13、妈妈带姐姐过去
14、爸爸妈妈坐船回来
15、妈妈带妹妹坐船过去
16、妈妈坐船回来
17、爸爸妈妈坐船过去

[ 本帖最后由 小码农 于 2014-12-28 15:27 编辑 ]
#3
小码农2014-12-28 15:27
#4
vvvcuu2015-01-12 17:28
这个问题应该属于那种所谓的商人过河问题吧.  

在C版块,beyondyf版主曾经写过关于类似问题的一片分析. 其中提到,解决这种问题的主要算法就是bfs和dfs.详细地址:

https://bbs.bccn.net/thread-436942-1-1.html
#5
一露2021-07-13 14:55
这道题有dfs的代码吗,能看看吗
1