[算法] - 人,狼,羊,白菜过河问题

每次只能带一样东西过桥,羊会吃白菜,狼会吃羊,但是狼不吃白菜,请问这个人要把这三样东西带过到河对岸?

思路:

a表示初始岸,b表示目的岸
1表示狼,2表示羊,3表示白菜

每次移动,人带一种东西或者不带;
每次移动,离开的一岸羊和狼或者白菜不能同时存在;
如果想把三种东西带到b岸:
- 人从a到b,每次都要带一种东西过河;
- 人从b到a,尽量不带,如果不带不可以,则随机带一个;

如果移动尝试失败,则换别的可能尝试,直到成功为止。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
var NC = {
a: [1,2,3], // a表示初始的一边,1表示狼,2表示羊,3表示白菜
b: [], // b表示另一边
status: 'a',
times: 1, // times尝试的次数
start: function () {
this.m('a', 'b', 0)
},
m: function (from, to, index) {
// 从from到to,带from下标为index的东西,index为-1时表示不带东西
console.log('第' + this.times + '次:初始值')
console.log('a边:' ,this.a)
console.log('b边:' ,this.b)
if (index == -1) {
console.log('人从:' + from + ' -> ' + to)
}else{
console.log('人尝试从 '+from+' 移动 ' + this[from][index] + ' 到 ' + to)
}
this.times++
var r, arr = [], len = this[from].length, v
if (index == -1) {
arr = this['b']
v = 0
}else{
for (var i = 0; i < len; i++) {
if (i != index) {
arr.push(this[from][i])
}else{
v = this[from][i]
}
}
}
r = this.checkFrom(arr)
if (!r) {
index++;
console.log('移动失败,进行下一次尝试')
console.log('--------------------')
this.m(from, to, index)
}else{
r = this.checkTo(to, v)
if (r) {
this.ms(from, to, v)
}else{
index++;
this.m(from, to, index)
}
}
},
ms: function (f, t, v) {
// 从f到t,带v表示的东西
var arr = [], l = this[f].length;
var sf = [], index = -1;
this.status = this.status == 'a' ? 'b' : 'a'
for (var i = 0; i < l; i++) {
if (this[f][i] != v) {
sf.push(this[f][i])
}else{
this[t].push(v);
}
}
this[f] = sf;
if (this.b.length == 3) {
this.sucLog()
return false
}
this.sucLog()
console.log('--------------------')
if (t != 'b') {
index = 0
}
this.m(t, f, index)
},
checkFrom: function (arr) {
// 检查离开的一岸剩下的物体是否可以同时存在
if (arr.length < 2) {
return true
}else{
return Math.abs(arr[0] - arr[1]) != 1
}
},
checkTo: function (t, v) {
// 检查是否与上一次重复带一个物体
if (!v) {
return true
}
// 重复r为true
var r = (t == 'a' && this.ta == v) || (t == 'b' && this.tb == v)
if (r) {
return false
}else{
if (t == 'a') {
this.ta = v
}
if (t == 'b') {
this.tb = v
}
return true
}
},
sucLog: function () {
// 打印结果
console.log('移动成功,结果为:')
console.log('a边:' ,this.a)
console.log('b边:' ,this.b)
console.log('人在' + this.status + '边')
}
}

这是一种尝试的方法,还有一种方法:列出所有状态,用宽搜思想去遍历出所有的可能性。