華容道是一個(gè)有益的智力游戲，游戲規(guī)則不再贅述。用計(jì)算機(jī)求解華容道也是一道不錯(cuò)的編程練習(xí)題，為了尋求最少步數(shù)，求解程序一般用廣度優(yōu)先搜索算法。華容道的一種常見開局如圖 1 所示。

廣度優(yōu)先搜索算法求解華容道的基本步驟：

1. 準(zhǔn)備兩個(gè)“全局變量”，隊(duì)列 Q 和和集合 S，S 代表“已知局面”。初時(shí) Q 和 S 皆為空。
2. 將初始局面加入隊(duì)列 Q 的末尾，并將初始局面設(shè)為已知。
3. 當(dāng)隊(duì)列不為空時(shí)，從 Q 的隊(duì)首取出當(dāng)前局面 curr。如果隊(duì)列為空則結(jié)束搜索，表明無解。
4. 如果 curr 是最終局面（曹操位于門口，圖 2），則結(jié)束搜索，否則繼續(xù)到第 5 步。
5. 考慮 curr 中每個(gè)可以移動的棋子，試著上下左右移動一步，得到新局面 next，如果新局面未知（next ∉ S），則把它加入隊(duì)列 Q，并設(shè)為已知。這一步可能產(chǎn)生多個(gè)新局面。
6. 回到第2步。

其中“局面已知”并不要求每個(gè)棋子的位置相同，而是指棋子的投影的形狀相同（代碼中用 mask 表示），例如交換圖 1 中的張飛和趙云并不產(chǎn)生新局面，這一規(guī)定可以大大縮小搜索空間。

以上步驟很容易轉(zhuǎn)換為 C++ 代碼，這篇文章重點(diǎn)關(guān)注的是第 5 步的實(shí)現(xiàn)。

// 第 1 步 
std::unordered_set<Mask> seen; 
std::deque<State> queue; 
  
// 第 2 步 
State initial; 
// 填入 initial，略。 
queue.push_back(initial); 
seen.insert(initial.toMask()); 
  
// 第 3 步 
while (!queue.empty()) 
{ 
  const State curr = queue.front(); 
  queue.pop_front(); 
  
  // 第 4 步 
  if (curr.isSolved()) 
    break; 
  
  // 第 5 步 
  for (const State& next : curr.moves()) 
  { 
    auto result = seen.insert(next.toMask()); 
    if (result.second) 
      queue.push_back(next); 
  } 
} 

在以上原始實(shí)現(xiàn)中，curr.move() 將返回一個(gè) std::vector<State> 臨時(shí)對象。一種節(jié)省開銷的辦法是準(zhǔn)備一個(gè) std::vector<State> “涂改變量”，讓 curr.move() 反復(fù)修改它，比如改成：

// 第 1 步新增一個(gè) scratch 變量 
std::vector<State> nextMoves; 
  
// 第 3 步 
while (!queue.empty()) 
{ 
  // ... 
  // 第 5 步 
  curr.fillMoves(&nextMoves); 
  for (const State& next : nextMoves) 
  { /* 略 */ } 
} 

還有一種徹底不用這個(gè) std::vector<State> 的辦法，把一部分邏輯以 lambda 的形式傳給 curr.move()，代碼的結(jié)構(gòu)基本不變：

// 第 3 步 
while (!queue.empty()) 
{ 
  // ... 
  // 第 5 步 
  curr.move([&seen, &queue](const State& next) { 
    auto result = seen.insert(next.toMask()); 
    if (result.second) 
      queue.push_back(next); 
  }); 
} 

這樣一來，主程序的邏輯依然清晰，不必要的開銷也降到了最小。

在我最早的實(shí)現(xiàn)中，curr.move() 的參數(shù)是 const std::function<void(const State&)> &，但是我發(fā)現(xiàn)這里每次構(gòu)造 std::function<void(const State&)> 對象都會分配一次內(nèi)存，似乎有些不值。因此在現(xiàn)在的實(shí)現(xiàn)中 curr.move() 是個(gè)函數(shù)模板，這樣就能自動匹配lambda參數(shù)（通常是個(gè) struct 對象），省去了 std::function的內(nèi)存分配。

本文完整的代碼見 https://github.com/chenshuo/recipes/…/puzzle/huarong.cc，需用 GCC 4.7 編譯，求解圖 1 的題目的耗時(shí)約幾十毫秒。

練習(xí)：修改程序，打印每一步移動棋子的情況。

原文鏈接：http://coolshell.cn/articles/10476.html