- //********************************************************************************//
- //
- // Missionaies and cannibals problem
- // @author zcloud
- // @date 2015.11.7
- // @reference https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
- //
- //********************************************************************************//
- #include <iostream>
- #include <stack>
- #include <vector>
- #include <deque>
- using namespace std;
- typedef struct State{
- int m;//野人
- int c;//传教士
- int p;//船位置
- bool opValid(int b)//is the operation valid?
- {
- bool bRet = false;
- if (0 == m && 0 == c) bRet = false;
- else if (0 == c && m <= b) bRet = true;
- else bRet = (c >= m && m + c <= b) ? true : false;
- return bRet;
- };
- bool valid(int n)//is the state valid;
- {
- return m >= 0 && c >= 0 && c >= m && c <= n && m <= n;
- }
- State operator-(State s)
- {
- State bRet;
- bRet = { m-s.m, c-s.c, p-s.p};
- return bRet;
- }
- State operator+(State s)
- {
- State bRet;
- bRet = { m + s.m, c + s.c, p+s.p};
- return bRet;
- }
- bool equals(State s){ return m == s.m && c == s.c && p == s.p; }
- }Operate;
- vector<Operate> genOperations(int n, int b)
- {
- vector<Operate> operations;
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- Operate op = { i, j, 1 };
- if (op.opValid(b)) operations.push_back(op);
- }
- }
- return operations;
- }
- vector<State> children(int n, State s, vector<State> operations)
- {
- vector<State> bRet;
- for (int i = 0, size = operations.size(); i < size; i++)
- {
- State newState = s.p == 0 ? s + operations[i] : s - operations[i];
- if(newState.valid(n)) bRet.push_back(newState);
- }
- return bRet;
- }
- bool check(State s, stack<State> ps, stack<State> nps, stack<State> nss)
- {
- deque<State> psQ = ps._Get_container();
- deque<State> npsQ = nps._Get_container();
- deque<State> nssQ = nss._Get_container();
- for (int i = 0, len = psQ.size(); i < len; i++)
- {
- if (psQ[i].equals(s)) return false;
- }
- for (int i = 0, len = npsQ.size(); i < len; i++)
- {
- if (npsQ[i].equals(s)) return false;
- }
- for (int i = 0, len = nssQ.size(); i < len; i++)
- {
- if (nssQ[i].equals(s)) return false;
- }
- return true;
- }
- void printPath(stack<State> ps)
- {
- deque<State> psQ = ps._Get_container();
- for (int i = 0, len = psQ.size(); i < len; i++)
- {
- printf("(%d, %d, %d)\\n", psQ[i].m, psQ[i].c, psQ[i].p);
- }
- }
- int main()
- {
- bool success = false;
- int n = 0;
- int b = 0;
- printf("input missionaries,cannibals numbers and boat capacity\\n");
- cin >> n >> b;
- //init state
- State s0 = { n, n, 1 };
- State sg = { 0, 0, 0 };
- State sc = s0;
- //init table
- stack<State> ps, nps, nss;
- ps.push(s0);
- nps.push(s0);
- //generate operations
- printf("operations:\\n");
- vector<State> operations = genOperations(n, b);
- for (int i = 0, size = operations.size(); i < size; i++)
- {
- printf("(%d, %d, %d) ", operations[i].m, operations[i].c, operations[i].p);
- }
- printf("\\n======================================================================\\n");
- while (!nps.empty())
- {
- if (sc.equals(sg))
- {
- success = true;
- break;
- }
- //update nps table
- vector<State> _children = children(n, sc, operations);
- //for (int i = 0, size = _children.size(); i < size; i++)
- //{
- // printf("(%d, %d, %d) ", _children[i].m, _children[i].c, _children[i].p);
- //}
- //printf("\\n================================================================\\n");
- if (!_children.empty())
- {
- for (int i = 0, size = _children.size(); i < size; i++)
- {
- if (check(_children[i], ps, nps, nss) == true)
- {
- nps.push(_children[i]);
- }
- }
- sc = nps.top();
- nps.pop();
- ps.push(sc);
- }
- else//none children
- {
- while (!ps.empty() && sc.equals(ps.top()))//backtracking
- {
- nss.push(sc);
- ps.pop();
- nps.pop();
- sc = nps.top();
- if (sc.equals(ps.top()))
- {
- nss.push(sc);
- ps.pop();
- nps.pop();
- sc = nps.top();
- break;
- }
- }
- ps.push(sc);
- }
- }
- if (success)
- {
- printf("success:\\n");
- printPath(ps);
- }
- else
- {
- printf("failed!\\n");
- }
- system("pause");
- }
- //该片段来自于http://www.codesnippet.cn/detail/2811201514114.html
来源: http://www.codesnippet.cn/detail/2811201514114.html