一道有意思的编程思考题：【妖怪和和尚过河问题】
无意中看到这么一道题，觉得很有意思，题目如下：
有三个和尚和三个妖怪要利用唯一的一条小船过河，这条小船一次只能载两个人，同时，无论是在河的两岸还是在船上，只要妖怪的数量大于和尚的数量，妖怪们就会将和尚吃掉。现在需要选择一种过河的安排，保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。
看完题目，首先想到的是暴力搜索。不断地穷举下一步的可能性，直到最终达成目标。因为搜索过程中可能会有重复的状态，所以需要对状态进行哈希。
如何表示当前的状态？首先想到的是用多维数组进行哈希。我们可以用一个四维数组（其实完全可以用二维，左边僧人妖怪的数量确定后，相应地就能计算右边了，需要多一步运算），假设左岸僧人和妖怪数量分别是 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 numberfunction 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 arrayfunction 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->------------------完整代码点 这里。
