無意間看到這麼一道題,覺得很有意思:
有三個和尚與三個妖怪要利用唯一的一條小船過河,小船一次最多載兩人。無論在河的哪一岸或船上,只要妖怪數量大於和尚數量,和尚就會被吃掉。請設計一種過河安排,讓所有和尚與妖怪都能安全過河。
第一反應通常是暴力搜尋——不斷枚舉下一步的所有可能,直到抵達目標狀態。由於過程中會出現重複的狀態,必須做狀態哈希來避免無限繞圈。
最樸素的作法是用多維陣列。用四維陣列分别表示左岸僧人 a、左岸妖怪 b、右岸僧人 c、右岸妖怪 d,以 [a][b][c][d] = true 表示該狀態走過了。其實二維就夠——左岸確定後右岸自然可推得,只是多一步計算。
但這裡有個漏洞:船在左岸或在右岸是兩種不同情況,所以還得多一維,用 [a][b][c][d][1] 表示船在左、[a][b][c][d][0] 表示船在右。邏輯上完全可行,問題是 JavaScript 操作多維陣列實在麻煩,於是繼續思考能否壓縮。
觀察初始狀態 [3, 3, 0, 0, 1]:搜尋過程中每個數字都不會超過 3,取值範圍只有 0 到 3——這不就是四進位嗎?於是可以把狀態壓縮成一個四進位數。但四進位算起來還是不順手,而每一位四進位恰好可拆成兩位二進位,於是 3300 這類狀態就能轉成二進位來處理,位運算瞬間變得方便許多。
考量到船的位置比較特殊,最後決定前四維用一個二進位數表示,船的位置另外用一維處理,整體以二維陣列做哈希。
先把 [3, 3, 0, 0] 轉成二進位為 11110000 的數字:
// 陣列轉數字
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;
}
反過來的逆運算:
// 數字轉陣列
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('------------------');
// 回溯
hash[num][pos] = false;
ans.pop();
return;
}
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 {
// 右岸到左岸
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);
}
}
}
// 回溯
hash[num][pos] = false;
ans.pop();
}
每次依船的位置枚舉下一個狀態,並用一個小函數判斷某岸的僧人與妖怪數量組合是否安全:
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 ------------------
這道題有意思的地方在於:它同時考了狀態設計、位運算壓縮與搜尋回溯。把狀態壓成一個整數之後,哈希的實作與效能都清爽很多,這是在其他語言中比較少有機會練習到的技巧。