代码框架

  1. // version 1
  2. // Typical backtracking procedure
  3. void recursion(state s)
  4. {
  5.     if( base(s) )
  6.         return ;
  8.     for each substate ss
  9.         mark ss
  11.         recursion (ss)
  13.         unmark ss
  14. }
  16. // version 2
  17. int ans = 最坏情况, now;  // now为当前答案
  18. void dfs(传入数值) {
  19.     if (到达目的地) ans = 从当前解与已有解中选最优;
  20.     for (遍历所有可能性)
  21.         if (可行) {
  22.             进行操作;
  23.             dfs(缩小规模);
  24.             撤回操作;
  25.         }
  26. }
  28. // version 3
  29.  * Backtracking(state)
  30.  *         if invalid(state)    //e.g. we reached a # or the location is already visited
  31.  *             return
  32.  *
  33.  *         if found_solution(state)
  34.  *             mark_solution_found
  35.  *             return
  36.  *
  37.  *         for each child_state of state
  38.  *             state' = do changes in state
  39.  *
  40.  *             Backtracking(state')
  41.  *
  42.  *             state = undo changes in state'