無意中看到這麼一道題,覺得很有意思,題目如下:
有三個和尚和三個妖怪要利用唯一的一條小船過河,這條小船一次只能載兩個人,同時,無論是在河的兩岸還是在船上,只要妖怪的數量大於和尚的數量,妖怪們就會將和尚吃掉。現在需要選擇一種過河的安排,保證和尚和妖怪都能過河且和尚不能被妖怪吃掉。
看完題目,首先想到的是暴力搜索。不斷地窮舉下一步的可能性,直到最終達成目標。因為搜索過程中可能會有重復的狀態,所以需要對狀態進行哈希。
如何表示當前的狀態?首先想到的是用多維數組進行哈希。我們可以用一個四維數組(其實完全可以用二維,左邊僧人妖怪的數量確定後,相應地就能計算右邊了,需要多一步運算),假設左岸僧人和妖怪數量分別是 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->
------------------
完整代碼點 這裡。