摘要：不斷地窮舉下一步的可能性，直到最終達(dá)成目標(biāo)。表示船在左邊表示船在右邊打印答案妖怪過河數(shù)僧人過河數(shù)船上是否安全左岸是否安全右岸是否安全過河后的數(shù)據(jù)過河后的數(shù)據(jù)簡(jiǎn)單地看下深度優(yōu)先搜索的函數(shù)，每次根據(jù)船所在的位置，枚舉下個(gè)狀態(tài)值。

無意中看到這么一道題，覺得很有意思，題目如下：

有三個(gè)和尚和三個(gè)妖怪要利用唯一的一條小船過河，這條小船一次只能載兩個(gè)人，同時(shí)，無論是在河的兩岸還是在船上，只要妖怪的數(shù)量大于和尚的數(shù)量，妖怪們就會(huì)將和尚吃掉。現(xiàn)在需要選擇一種過河的安排，保證和尚和妖怪都能過河且和尚不能被妖怪吃掉。

看完題目，首先想到的是暴力搜索。不斷地窮舉下一步的可能性，直到最終達(dá)成目標(biāo)。因?yàn)樗阉鬟^程中可能會(huì)有重復(fù)的狀態(tài)，所以需要對(duì)狀態(tài)進(jìn)行哈希。

如何表示當(dāng)前的狀態(tài)？首先想到的是用多維數(shù)組進(jìn)行哈希。我們可以用一個(gè)四維數(shù)組（其實(shí)完全可以用二維，左邊僧人妖怪的數(shù)量確定后，相應(yīng)地就能計(jì)算右邊了，需要多一步運(yùn)算），假設(shè)左岸僧人和妖怪?jǐn)?shù)量分別是 a 和 b，右岸僧人妖怪?jǐn)?shù)量分別是 c 和 d，那么我們可以用 [a][b][c][d]=true 表示這種情況，也就是該狀態(tài)已經(jīng)被搜索過了。這樣做還有個(gè)漏洞，船在左右兩邊是不同的情況，所以還需要一個(gè)維度來表示船的位置，那么可以這樣，增加一維，用 [a][b][c][d][1]=true 表示船在左邊的情況，用 [a][b][c][d][0]=true 表示船在右邊的情況。這樣來表示狀態(tài)是完全可以的，但是眾所周知 JavaScript 下表示多維數(shù)組非常的麻煩，所以進(jìn)一步思考能不能將狀態(tài)壓縮。

繼續(xù)看，最開始時(shí)的狀態(tài)，如上可以表示為 [3][3][0][0][1]，之后的搜索過程中，狀態(tài)中的數(shù)字不可能大于 3，也就是數(shù)字的范圍在 0~3 中，這不是赤裸裸的四進(jìn)制數(shù)嗎？于是我們可以將該狀態(tài)壓縮到一個(gè)四進(jìn)制數(shù) 330001 中，但是四進(jìn)制畢竟操作起來不大方便，能不能轉(zhuǎn)為二進(jìn)制？答案很明顯，一個(gè)四進(jìn)制數(shù)可以拆成兩個(gè)二進(jìn)制，這樣就好辦了，將四進(jìn)制的 33001 可以轉(zhuǎn)成二進(jìn)制 1111000001，二進(jìn)制的各種運(yùn)算就方便多了！

考慮到最后一個(gè)維度的特殊情況，最終我決定將前四個(gè)維度用一個(gè)二進(jìn)制來處理，第五個(gè)維度（船的位置）多帶帶處理，用一個(gè)二維數(shù)組進(jìn)行狀態(tài)哈希。

很顯然，我們需要能將數(shù)組和二進(jìn)制數(shù)互換的函數(shù)。

簡(jiǎn)單寫了兩個(gè)互換函數(shù)，將數(shù)組轉(zhuǎn)為數(shù)字的。比如將 [3, 3, 0, 0] 轉(zhuǎn)為二進(jìn)制大小為 11110000 的數(shù)字：

// 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;
}

將數(shù)字轉(zhuǎn)為數(shù)組的，為以上函數(shù)的逆運(yùn)算：

// 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;
}

接下去就非常簡(jiǎn)單了，進(jìn)行深度優(yōu)先搜索，每次搜索枚舉下一個(gè)可能的狀態(tài)，對(duì)該狀態(tài)進(jìn)行哈希，并把該狀態(tài)存入答案數(shù)組中，枚舉完進(jìn)行回溯。

// 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++) // 妖怪過河數(shù)
      for (var j = 0; j <= l_sNum; j++) {  // 僧人過河數(shù)

        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;

        // 過河后的數(shù)據(jù)
        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;

        // 過河后的數(shù)據(jù)
        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();
}

簡(jiǎn)單地看下深度優(yōu)先搜索的函數(shù)，每次根據(jù)船所在的位置，枚舉下個(gè)狀態(tài)值。這里我寫了個(gè) checkIfSafe 函數(shù)來判斷當(dāng)前數(shù)量的僧人和妖怪在一起，會(huì)不會(huì)有危險(xiǎn)。函數(shù)非常簡(jiǎn)單：

function checkIfSafe(sNum, yNum) {
  return sNum === 0 || sNum >= yNum;
}

最后的最后，解法有四種，大概是這個(gè)樣子：

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->
------------------

完整代碼點(diǎn) 這里。