无意中看到这么一道题,觉得很有意思,问题以下:有三个和尚和三个妖怪要应用唯一的一条小船过河,这条小船一次只能载两个人,同时,无论是在河的两岸照样在船上,只需妖怪的数目大于和尚的数目
无意中看到这么一道题,觉得很有意思,问题以下:
有三个和尚和三个妖怪要应用唯一的一条小船过河,这条小船一次只能载两个人,同时,无论是在河的两岸照样在船上,只需妖怪的数目大于和尚的数目,妖怪们就会将和尚吃掉。如今须要挑选一种过河的部署,保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。
看完问题,起首想到的是暴力搜刮。不断地穷举下一步的能够性,直到终究杀青目的。由于搜刮过程当中能够会有反复的状况,所以须要对状况举行哈希。
怎样示意当前的状况?起首想到的是用多维数组举行哈希。我们能够用一个四维数组(实在完全能够用二维,左侧和尚妖怪的数目肯定后,响应地就能够盘算右侧了,须要多一步运算),假定左岸和尚和妖怪数目分别是 a 和 b,右岸和尚妖怪数目分别是 c 和 d,那末我们能够用 [a][b][c][d]=true
示意这类状况,也就是该状况已被搜刮过了。如许做另有个破绽,船在摆布双方是差别的状况,所以还须要一个维度来示意船的位置,那末能够如许,增添一维,用 [a][b][c][d][1]=true
示意船在左侧的状况,用 [a][b][c][d][0]=true
示意船在右侧的状况。如许来示意状况是完全能够的,然则尽人皆知 Javascript 下示意多维数组异常的贫苦,所以进一步思索能不能将状况紧缩。
继承看,最开始时的状况,如上能够示意为 [3][3][0][0][1]
,以后的搜刮过程当中,状况中的数字不能够大于 3,也就是数字的范围在 0~3 中,这不是光秃秃的四进制数吗?因而我们能够将该状况紧缩到一个四进制数 330001
中,然则四进制毕竟操纵起来不大轻易,能不能转为二进制?答案很明显,一个四进制数能够拆成两个二进制,如许就好办了,将四进制的 33001
能够转成二进制 1111000001
,二进制的种种运算就轻易多了!
斟酌到末了一个维度的特殊状况,终究我决定将前四个维度用一个二进制来处置惩罚,第五个维度(船的位置)零丁处置惩罚,用一个二维数组举行状况哈希。
很显然,我们须要能将数组和二进制数交换的函数。
简朴写了两个交换函数,将数组转为数字的。比方将 [3, 3, 0, 0]
转为二进制大小为 11110000
的数字:
// array to number
function aton(a) {
var sum = 0;
for (var i = a.length; i--; ) {
var index = 3 - i
, item = a[i];
(item & 1) && (sum |= (1 <<(index <<1)));
(item & 2) && (sum |= (1 <<((index <<1) | 1)));
}
return sum;
}
将数字转为数组的,为以上函数的逆运算:
// number to array
function ntoa(n) {
var a = [];
for (var i = 0; i <4; i++) {
var num = 0
, index = 3 - i;
num |= n & (1 <<(index <<1)) ? 1 : 0;
num |= n & ((1 <<((index <<1) | 1))) ? 2 : 0;
a.push(num);
}
return a;
}
接下去就异常简朴了,举行深度优先搜刮,每次搜刮罗列下一个能够的状况,对该状况举行哈希,并把该状况存入答案数组中,罗列完举行回溯。
// pos == 1 示意船在左侧
// pos == 0 示意船在右侧
function dfs(num, pos) {
if (hash[num][pos])
return;
hash[num][pos] = true;
var a = ntoa(num);
var l_sNum = a[0];
var l_yNum = a[1];
var r_sNum = a[2];
var r_yNum = a[3];
pos ? a.push('left') : a.push('right');
ans.push(a);
if (num === 15) { // [0, 0, 3, 3]
// 打印答案
ans.concat().forEach(function(item) {
console.log(item.toString() + '->');
});
console.log('------------------');
// backtrace
hash[num][pos] = false;
ans.pop();
return;
}
// left to right
if (pos) {
for (var i = 0; i <= l_yNum; i++) // 妖怪过河数
for (var j = 0; j <= l_sNum; j++) { // 和尚过河数
if (i + j === 0)
continue;
// 船上是不是平安
if (!checkIfSafe(j, i))
continue;
// 左岸是不是平安
if (!checkIfSafe(l_sNum - j, l_yNum - i))
continue;
// 右岸是不是平安
if (!checkIfSafe(r_sNum + j, r_yNum + i))
continue;
if (i + j > 2)
break;
// 过河后的数据
var b = [l_sNum - j, l_yNum - i, r_sNum + j, r_yNum + i];
dfs(aton(b), 0);
}
} else { // right to left
for (var i = 0; i <= r_yNum; i++)
for (var j = 0; j <= r_sNum; j++) {
if (i + j === 0)
continue;
if (!checkIfSafe(j, i))
continue;
if (!checkIfSafe(r_sNum - j, r_yNum - i))
continue;
if (!checkIfSafe(l_sNum + j, l_yNum + i))
continue;
if (i + j > 2)
break;
// 过河后的数据
var b = [l_sNum + j, l_yNum + i, r_sNum - j, r_yNum - i];
dfs(aton(b), 1);
}
}
// backtrace
hash[num][pos] = false;
ans.pop();
}
简朴地看下深度优先搜刮的函数,每次依据船地点的位置,罗列下个状况值。这里我写了个 checkIfSafe 函数来推断当前数目的和尚和妖怪在一起,会不会有风险。函数异常简朴:
function checkIfSafe(sNum, yNum) {
return sNum === 0 || sNum >= yNum;
}
末了的末了,解法有四种,大概是这个模样:
3,3,0,0,left->
2,2,1,1,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
1,1,2,2,left->
0,0,3,3,right->
------------------
3,3,0,0,left->
2,2,1,1,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
0,2,3,1,left->
0,0,3,3,right->
------------------
3,3,0,0,left->
3,1,0,2,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
1,1,2,2,left->
0,0,3,3,right->
------------------
3,3,0,0,left->
3,1,0,2,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
0,2,3,1,left->
0,0,3,3,right->
------------------
完全代码点 这里。