Technorati 标记: ,

 

原题在这里：

http://www2.stetson.edu/~efriedma/holiday/2011/index.html

 

题目：

有这样一个迷宫，从2011开始，不能回头，只能“朝前”走，走出迷宫的时候需要变成2012.

image

例如从2011开始，有+7,/2两种选择，选择/2后，又有+7,x3/-5三种选择。

 

解法：

其实就是2011为根的子树，不断的生成下一层的节点，直到节点值为2012。

dfs遍历肯定不现实的，bfs算是比较适合的方法了。不过有更快捷的办法，我使用的是最原始的bfs。

运算方式有四种，位置有三种，分别用枚举表示。

 

代码：

代码写的很长了，100行以内应该是没问题的，即使是使用我的这种笨方法o(╯□╰)o。为了条理清楚些，就多定义了些函数。

Code Snippet
  1. /*
  2. * =====================================================================================
  3. *       Filename:  puzzle.cpp
  4. *    Description:  
  5. *
  6. *        Version:  1.0
  7. *        Created:  11/16/2012 04:34:49 PM
  8. *
  9. *         Author:  zhy (), izualzhy@163.com
  10. * =====================================================================================
  11. */
  12.  
  13. #include <iostream>
  14. #include <vector>
  15. #include <queue>
  16. #include <string>
  17. using namespace std;
  18.  
  19. class PuzzleGuessor {
  20. public:
  21.     /*可选的数学运算*/
  22.     enum Op {
  23.         OpNone,
  24.         AddSeven,
  25.         DivTwo,
  26.         MultiThree,
  27.         SubFive,
  28.         OpCount
  29.     };
  30.  
  31.     /*位置，由位置和数学运算则可以推断下一步可选的运算方式*/
  32.     enum Position {
  33.         Left,
  34.         Middle,
  35.         Right
  36.     };
  37.  
  38.     /*节点，记录当前的计算结果，位置和到达位置前的运算方式 */
  39.     struct TreeNode {
  40.         TreeNode(double d, Op op, Position position)
  41.             : data(d)
  42.             , oper(op)
  43.             , pos(position)
  44.         {
  45.         }
  46.  
  47.         double data;
  48.         Op oper;
  49.         Position pos;
  50.         vector<TreeNode*> children;
  51.     };
  52.  
  53.     PuzzleGuessor();
  54.     void BuildTree();//构造树
  55.  
  56. private:
  57.     queue<TreeNode*> q;
  58.     TreeNode* root;
  59.     string OpTable[OpCount];//运算对应的字符串表，输出用
  60.     string result;
  61.     bool CreateNewChildForNode(TreeNode* node);//由节点处根据下一步可进行的运算产生下一层节点
  62.     bool CalcNextFromLeft(TreeNode* node);//在左端时可能的节点
  63.     bool CalcNextFromMiddle(TreeNode* node);//中间位置
  64.     bool CalcNextFromRight(TreeNode* node);//右端
  65.     bool Achieve2012(TreeNode* node);
  66.     bool Find(TreeNode* node, TreeNode* objNode);
  67. };
  68.  
  69. PuzzleGuessor::PuzzleGuessor()
  70. {
  71.     root = new TreeNode(2011.0, OpNone, Left);
  72.     TreeNode* child1 = new TreeNode(root->data + 7, AddSeven, Middle);
  73.     TreeNode* child2 = new TreeNode(root->data / 2, DivTwo, Middle);
  74.     root->children.push_back(child1);
  75.     root->children.push_back(child2);
  76.     q.push(child1);
  77.     q.push(child2);
  78.  
  79.     OpTable[OpNone] = "none";
  80.     OpTable[AddSeven] = "+7";
  81.     OpTable[DivTwo] = "/2";
  82.     OpTable[MultiThree] = "x3";
  83.     OpTable[SubFive] = "-5";
  84.     BuildTree();
  85. }
  86.  
  87. void PuzzleGuessor::BuildTree()
  88. {
  89.     result.clear();
  90.     while (!q.empty())
  91.     {
  92.         TreeNode* node = q.front();
  93.         CreateNewChildForNode(node);
  94.         for ( int i=0; i<node->children.size(); ++i)
  95.         {
  96.             if (node->children[i]->data - 2012 < 1e-6 && 2012 - node->children[i]->data < 1e-6)
  97.             {
  98.                 cout << "Achieve 2012!\t" << node->children[i]->data << endl;
  99.                 Find(root, node->children[i]);
  100.                 cout << result << endl;
  101.                 result.clear();
  102.                 ///*如果不retunr，则会一直计算下去   */
  103.                 //return;
  104.             }
  105.             q.push(node->children[i]);
  106.         }
  107.         q.pop();
  108.     }
  109. }
  110.  
  111. bool PuzzleGuessor::Find(TreeNode* node, TreeNode* objNode)
  112. {
  113.     if (node == NULL)
  114.         return false;
  115.     if (node == objNode)
  116.     {
  117.         result = OpTable[node->oper];
  118.         return true;
  119.     }
  120.     for ( int i=0; i<node->children.size(); ++i)
  121.     {
  122.        if( Find(node->children[i], objNode) )
  123.        {
  124.            //cout << node->data << endl;
  125.            if (OpNone == node->oper)
  126.                result.insert(0, "2011");
  127.            else
  128.                result.insert(0,OpTable[node->oper]);
  129.            return true;
  130.        }
  131.     }
  132.  
  133.     return false;
  134. }
  135.  
  136. bool PuzzleGuessor::CreateNewChildForNode(TreeNode* node)
  137. {
  138.     if (node == NULL)
  139.         return false;
  140.  
  141.     switch (node->pos)
  142.     {
  143.         case Left:
  144.             CalcNextFromLeft(node);
  145.             break;
  146.         case Middle:
  147.             CalcNextFromMiddle(node);
  148.             break;
  149.         case Right:
  150.             CalcNextFromRight(node);
  151.             break;
  152.     }
  153. }
  154.  
  155. bool PuzzleGuessor::CalcNextFromLeft(TreeNode* node)
  156. {
  157.     if (node == NULL)
  158.         return false;
  159.  
  160.     switch (node->oper)
  161.     {
  162.         case AddSeven:
  163.             {
  164.                 TreeNode* newNode = new TreeNode(node->data / 2, DivTwo, Middle);
  165.                 node->children.push_back(newNode);
  166.                 break;
  167.             }
  168.         case DivTwo:
  169.             {
  170.                 TreeNode* newNode = new TreeNode(node->data + 7, AddSeven, Middle);
  171.                 node->children.push_back(newNode);
  172.                 break;
  173.             }
  174.         default:
  175.             return false;
  176.     }
  177.  
  178.     return true;
  179. }
  180. bool PuzzleGuessor::CalcNextFromMiddle(TreeNode* node)
  181. {
  182.     if (node == NULL)
  183.         return false;
  184.  
  185.     if (node->oper == AddSeven || node->oper == DivTwo)
  186.     {
  187.         TreeNode* newNode = new TreeNode(node->data * 3, MultiThree, Right);
  188.         node->children.push_back(newNode);
  189.         newNode = new TreeNode(node->data - 5, SubFive, Right);
  190.         node->children.push_back(newNode);
  191.  
  192.         if (node->oper == AddSeven)
  193.         {
  194.             TreeNode* newNode = new TreeNode(node->data / 2, DivTwo, Left);
  195.             node->children.push_back(newNode);
  196.         }
  197.         else if (node->oper == DivTwo)
  198.         {
  199.             TreeNode* newNode = new TreeNode(node->data + 7, AddSeven, Left);
  200.             node->children.push_back(newNode);
  201.         }
  202.     }
  203.     else if (node->oper == MultiThree || node->oper == SubFive)
  204.     {
  205.         TreeNode* newNode = new TreeNode(node->data + 7, AddSeven, Left);
  206.         node->children.push_back(newNode);
  207.         newNode = new TreeNode(node->data / 2, DivTwo ,Left);
  208.         node->children.push_back(newNode);
  209.  
  210.         if (node->oper == MultiThree)
  211.         {
  212.             TreeNode* newNode = new TreeNode(node->data - 5, DivTwo, Right);
  213.             node->children.push_back(newNode);
  214.         }
  215.         else if (node->oper == SubFive)
  216.         {
  217.             TreeNode* newNode = new TreeNode(node->data * 3, MultiThree, Right);
  218.             node->children.push_back(newNode);
  219.         }
  220.     }
  221.     else
  222.     {
  223.         return false;
  224.     }
  225.  
  226.     return true;
  227. }
  228.  
  229. bool PuzzleGuessor::CalcNextFromRight(TreeNode* node)
  230. {
  231.     if (node == NULL)
  232.         return false;
  233.  
  234.     switch (node->oper)
  235.     {
  236.         case MultiThree:
  237.             {
  238.                 TreeNode* newNode = new TreeNode(node->data - 5, SubFive, Middle);
  239.                 node->children.push_back(newNode);
  240.                 break;
  241.             }
  242.         case SubFive:
  243.             {
  244.                 TreeNode* newNode = new TreeNode(node->data * 3, MultiThree, Middle);
  245.                 node->children.push_back(newNode);
  246.                 break;
  247.             }
  248.         default:
  249.             return false;
  250.     }
  251.  
  252.     return true;
  253. }
  254.  
  255. int main()
  256. {
  257.     PuzzleGuessor guesser;
  258.     return 0;
  259. }

部分输出：

Achieve 2012!    2012
2011+7/2+7/2+7x3-5/2+7x3-5/2+7x3-5x3-5/2+7/2+7/2+7/2+7x3-5+7
Achieve 2012!    2012
2011+7/2+7/2+7x3-5/2+7x3-5/2+7-5x3+7/2+7/2+7/2+7/2x3-5x3-5+7
Achieve 2012!    2012
2011+7/2+7/2+7x3-5x3-5+7/2+7/2+7/2+7/2x3-5/2+7x3-5x3-5+7/2+7
Achieve 2012!    2012
2011+7/2+7/2+7x3-5x3-5+7/2+7/2+7/2+7/2x3-5/2+7-5x3/2+7x3-5+7
Achieve 2012!    2012
2011+7/2+7/2+7-5x3/2+7x3-5+7/2+7/2+7/2x3-5/2+7x3-5x3-5+7/2+7
Achieve 2012!    2012
2011+7/2+7/2+7-5x3/2+7x3-5+7/2+7/2+7/2x3-5/2+7-5x3/2+7x3-5+7
Achieve 2012!    2012
2011+7/2+7/2+7-5x3/2+7/2+7x3-5/2+7-5x3+7/2+7/2x3-5x3-5+7/2+7
Achieve 2012!    2012
2011+7/2+7/2+7-5x3/2+7/2+7x3-5/2+7-5x3+7/2+7/2-5x3/2+7x3-5+7
Achieve 2012!    2012
2011+7/2+7/2+7-5x3/2+7/2+7-5x3/2+7x3-5/2+7x3-5+7/2+7/2x3-5+7