Technorati 標(biāo)記: 迷宮, bfs 原題在這里: http://www2.stetson.edu/~efriedma/holiday/2011/index.html 題目: 有這樣一個(gè)迷宮,從2011開始,不能回頭,只能“朝前”走,走出迷宮的時(shí)候需要變成2012.  例如從2011開始,有+7,/2兩種選擇,選擇/2后,又有+7,x3/-5三種選擇。 解法: 其實(shí)就是2011為根的子樹,不斷的生成下一層的節(jié)點(diǎn),直到節(jié)點(diǎn)值為2012。 dfs遍歷肯定不現(xiàn)實(shí)的,bfs算是比較適合的方法了。不過有更快捷的辦法,我使用的是最原始的bfs。 運(yùn)算方式有四種,位置有三種,分別用枚舉表示。 代碼: 代碼寫的很長(zhǎng)了,100行以內(nèi)應(yīng)該是沒問題的,即使是使用我的這種笨方法o(╯□╰)o。為了條理清楚些,就多定義了些函數(shù)。 Code Snippet - /*
- * =====================================================================================
- * Filename: puzzle.cpp
- * Description:
- *
- * Version: 1.0
- * Created: 11/16/2012 04:34:49 PM
- *
- * Author: zhy (), izualzhy@163.com
- * =====================================================================================
- */
-
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <string>
- using namespace std;
-
- class PuzzleGuessor {
- public:
- /*可選的數(shù)學(xué)運(yùn)算*/
- enum Op {
- OpNone,
- AddSeven,
- DivTwo,
- MultiThree,
- SubFive,
- OpCount
- };
-
- /*位置,由位置和數(shù)學(xué)運(yùn)算則可以推斷下一步可選的運(yùn)算方式*/
- enum Position {
- Left,
- Middle,
- Right
- };
-
- /*節(jié)點(diǎn),記錄當(dāng)前的計(jì)算結(jié)果,位置和到達(dá)位置前的運(yùn)算方式 */
- struct TreeNode {
- TreeNode(double d, Op op, Position position)
- : data(d)
- , oper(op)
- , pos(position)
- {
- }
-
- double data;
- Op oper;
- Position pos;
- vector<TreeNode*> children;
- };
-
- PuzzleGuessor();
- void BuildTree();//構(gòu)造樹
-
- private:
- queue<TreeNode*> q;
- TreeNode* root;
- string OpTable[OpCount];//運(yùn)算對(duì)應(yīng)的字符串表,輸出用
- string result;
- bool CreateNewChildForNode(TreeNode* node);//由節(jié)點(diǎn)處根據(jù)下一步可進(jìn)行的運(yùn)算產(chǎn)生下一層節(jié)點(diǎn)
- bool CalcNextFromLeft(TreeNode* node);//在左端時(shí)可能的節(jié)點(diǎn)
- bool CalcNextFromMiddle(TreeNode* node);//中間位置
- bool CalcNextFromRight(TreeNode* node);//右端
- bool Achieve2012(TreeNode* node);
- bool Find(TreeNode* node, TreeNode* objNode);
- };
-
- PuzzleGuessor::PuzzleGuessor()
- {
- root = new TreeNode(2011.0, OpNone, Left);
- TreeNode* child1 = new TreeNode(root->data + 7, AddSeven, Middle);
- TreeNode* child2 = new TreeNode(root->data / 2, DivTwo, Middle);
- root->children.push_back(child1);
- root->children.push_back(child2);
- q.push(child1);
- q.push(child2);
-
- OpTable[OpNone] = "none";
- OpTable[AddSeven] = "+7";
- OpTable[DivTwo] = "/2";
- OpTable[MultiThree] = "x3";
- OpTable[SubFive] = "-5";
- BuildTree();
- }
-
- void PuzzleGuessor::BuildTree()
- {
- result.clear();
- while (!q.empty())
- {
- TreeNode* node = q.front();
- CreateNewChildForNode(node);
- for ( int i=0; i<node->children.size(); ++i)
- {
- if (node->children[i]->data - 2012 < 1e-6 && 2012 - node->children[i]->data < 1e-6)
- {
- cout << "Achieve 2012!\t" << node->children[i]->data << endl;
- Find(root, node->children[i]);
- cout << result << endl;
- result.clear();
- ///*如果不retunr,則會(huì)一直計(jì)算下去 */
- //return;
- }
- q.push(node->children[i]);
- }
- q.pop();
- }
- }
-
- bool PuzzleGuessor::Find(TreeNode* node, TreeNode* objNode)
- {
- if (node == NULL)
- return false;
- if (node == objNode)
- {
- result = OpTable[node->oper];
- return true;
- }
- for ( int i=0; i<node->children.size(); ++i)
- {
- if( Find(node->children[i], objNode) )
- {
- //cout << node->data << endl;
- if (OpNone == node->oper)
- result.insert(0, "2011");
- else
- result.insert(0,OpTable[node->oper]);
- return true;
- }
- }
-
- return false;
- }
-
- bool PuzzleGuessor::CreateNewChildForNode(TreeNode* node)
- {
- if (node == NULL)
- return false;
-
- switch (node->pos)
- {
- case Left:
- CalcNextFromLeft(node);
- break;
- case Middle:
- CalcNextFromMiddle(node);
- break;
- case Right:
- CalcNextFromRight(node);
- break;
- }
- }
-
- bool PuzzleGuessor::CalcNextFromLeft(TreeNode* node)
- {
- if (node == NULL)
- return false;
-
- switch (node->oper)
- {
- case AddSeven:
- {
- TreeNode* newNode = new TreeNode(node->data / 2, DivTwo, Middle);
- node->children.push_back(newNode);
- break;
- }
- case DivTwo:
- {
- TreeNode* newNode = new TreeNode(node->data + 7, AddSeven, Middle);
- node->children.push_back(newNode);
- break;
- }
- default:
- return false;
- }
-
- return true;
- }
- bool PuzzleGuessor::CalcNextFromMiddle(TreeNode* node)
- {
- if (node == NULL)
- return false;
-
- if (node->oper == AddSeven || node->oper == DivTwo)
- {
- TreeNode* newNode = new TreeNode(node->data * 3, MultiThree, Right);
- node->children.push_back(newNode);
- newNode = new TreeNode(node->data - 5, SubFive, Right);
- node->children.push_back(newNode);
-
- if (node->oper == AddSeven)
- {
- TreeNode* newNode = new TreeNode(node->data / 2, DivTwo, Left);
- node->children.push_back(newNode);
- }
- else if (node->oper == DivTwo)
- {
- TreeNode* newNode = new TreeNode(node->data + 7, AddSeven, Left);
- node->children.push_back(newNode);
- }
- }
- else if (node->oper == MultiThree || node->oper == SubFive)
- {
- TreeNode* newNode = new TreeNode(node->data + 7, AddSeven, Left);
- node->children.push_back(newNode);
- newNode = new TreeNode(node->data / 2, DivTwo ,Left);
- node->children.push_back(newNode);
-
- if (node->oper == MultiThree)
- {
- TreeNode* newNode = new TreeNode(node->data - 5, DivTwo, Right);
- node->children.push_back(newNode);
- }
- else if (node->oper == SubFive)
- {
- TreeNode* newNode = new TreeNode(node->data * 3, MultiThree, Right);
- node->children.push_back(newNode);
- }
- }
- else
- {
- return false;
- }
-
- return true;
- }
-
- bool PuzzleGuessor::CalcNextFromRight(TreeNode* node)
- {
- if (node == NULL)
- return false;
-
- switch (node->oper)
- {
- case MultiThree:
- {
- TreeNode* newNode = new TreeNode(node->data - 5, SubFive, Middle);
- node->children.push_back(newNode);
- break;
- }
- case SubFive:
- {
- TreeNode* newNode = new TreeNode(node->data * 3, MultiThree, Middle);
- node->children.push_back(newNode);
- break;
- }
- default:
- return false;
- }
-
- return true;
- }
-
- int main()
- {
- PuzzleGuessor guesser;
- return 0;
- }
部分輸出: 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
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 |
|
常用鏈接
留言簿(5)
隨筆分類(18)
隨筆檔案(16)
最新隨筆
搜索
積分與排名
最新隨筆
最新評(píng)論

閱讀排行榜
評(píng)論排行榜
|
|