00001
00039 #include <iostream>
00040 #include <deque>
00041 #include <vector>
00042 using namespace std;
00043
00044
00045 class Node;
00046
00048 typedef Node* PNode;
00049
00050 typedef unsigned short int usint;
00051 typedef unsigned long int ulint;
00052
00059 class Node
00060 {
00061 private:
00062 inline bool CheckSezrani(usint misionari, usint kanibalove)
00063 {
00064 return (((misionari >= kanibalove) || (misionari == 0)) &&
00065 ((3-misionari) >= (3-kanibalove) || (misionari == 3)));
00066 }
00067 public:
00068
00069
00070 PNode root;
00071 vector<PNode> children;
00072
00074 usint misionari;
00076 usint kanibalove;
00078 usint lodka;
00079
00081 ulint visited;
00082
00083 Node() : root(NULL), misionari(3), kanibalove(3), lodka(1), visited((1 << ((3 << 3) | (3 << 1) | 1))) {};
00084 Node(PNode koren, usint mis, usint kan, usint lod, ulint vis) : root(koren), misionari(mis), kanibalove(kan), lodka(lod), visited(vis) {};
00085
00090 void GenStates();
00091
00096 void DumpPath();
00097 };
00098
00099
00100 void Node::DumpPath()
00101 {
00102 deque<PNode> lifo;
00103
00104 PNode current = this;
00105 lifo.push_back(current);
00106
00107 while (current->root != NULL)
00108 {
00109 current = current->root;
00110 lifo.push_back(current);
00111 }
00112
00113 while (lifo.size() > 0)
00114 {
00115 cout << "[M: " << lifo.back()->misionari << "][K: " << lifo.back()->kanibalove << "]";
00116 if (lifo.back()->lodka == 1) { cout << "[lodka] [ ]"; } else { cout << "[ ] [lodka]"; }
00117 cout << "[M: " << 3-lifo.back()->misionari << "][K: " << 3-lifo.back()->kanibalove << "]" << endl;
00118
00119 lifo.pop_back();
00120 }
00121 }
00122
00123 void Node::GenStates()
00124 {
00125 if ((misionari == 0) && (kanibalove == 0) && (lodka == 0)) { return; }
00126
00127
00128
00129 if ((lodka == 1) && (misionari > 0) && CheckSezrani(misionari-1,kanibalove))
00130 {
00131
00132 ulint stateBit = (1 << (((misionari-1) << 3) | (kanibalove << 1) | 0));
00133
00134 if ((visited & stateBit) == 0)
00135 { children.push_back(new Node(this,misionari-1,kanibalove,0,visited | stateBit)); }
00136 }
00137
00138 else if ((lodka == 0) && (misionari < 3) && CheckSezrani(misionari+1,kanibalove))
00139 {
00140
00141 ulint stateBit = (1 << (((misionari+1) << 3) | (kanibalove << 1) | 1));
00142
00143 if ((visited & stateBit) == 0)
00144 { children.push_back(new Node(this,misionari+1,kanibalove,1,visited | stateBit)); }
00145 }
00146
00147
00148
00149 if ((lodka == 1) && (misionari > 1) && CheckSezrani(misionari-2,kanibalove))
00150 {
00151
00152 ulint stateBit = (1 << (((misionari-2) << 3) | (kanibalove << 1) | 0));
00153
00154 if ((visited & stateBit) == 0)
00155 { children.push_back(new Node(this,misionari-2,kanibalove,0,visited | stateBit)); }
00156 }
00157
00158 else if ((lodka == 0) && (misionari < 2) && CheckSezrani(misionari+2,kanibalove))
00159 {
00160
00161 ulint stateBit = (1 << (((misionari+2) << 3) | (kanibalove << 1) | 1));
00162
00163 if ((visited & stateBit) == 0)
00164 { children.push_back(new Node(this,misionari+2,kanibalove,1,visited | stateBit)); }
00165 }
00166
00167
00168
00169 if ((lodka == 1) && (kanibalove > 0) && CheckSezrani(misionari,kanibalove-1))
00170 {
00171
00172 ulint stateBit = (1 << ((misionari << 3) | ((kanibalove-1) << 1) | 0));
00173
00174 if ((visited & stateBit) == 0)
00175 { children.push_back(new Node(this,misionari,kanibalove-1,0,visited | stateBit)); }
00176 }
00177
00178 else if ((lodka == 0) && (kanibalove < 3) && CheckSezrani(misionari,kanibalove+1))
00179 {
00180
00181 ulint stateBit = (1 << ((misionari << 3) | ((kanibalove+1) << 1) | 1));
00182
00183 if ((visited & stateBit) == 0)
00184 { children.push_back(new Node(this,misionari,kanibalove+1,1,visited | stateBit)); }
00185 }
00186
00187
00188
00189 if ((lodka == 1) && (kanibalove > 1) && CheckSezrani(misionari,kanibalove-2))
00190 {
00191
00192 ulint stateBit = (1 << ((misionari << 3) | ((kanibalove-2) << 1) | 0));
00193
00194 if ((visited & stateBit) == 0)
00195 { children.push_back(new Node(this,misionari,kanibalove-2,0,visited | stateBit)); }
00196 }
00197
00198 else if ((lodka == 0) && (kanibalove < 2) && CheckSezrani(misionari,kanibalove+2))
00199 {
00200
00201 ulint stateBit = (1 << ((misionari << 3) | ((kanibalove+2) << 1) | 1));
00202
00203 if ((visited & stateBit) == 0)
00204 { children.push_back(new Node(this,misionari,kanibalove+2,1,visited | stateBit)); }
00205 }
00206
00207
00208 if ((lodka == 1) && (misionari > 0) && (kanibalove > 0) && CheckSezrani(misionari-1,kanibalove-1))
00209 {
00210 ulint stateBit = (1 << (((misionari-1) << 3) | ((kanibalove-1) << 1) | 0));
00211
00212 if ((visited & stateBit) == 0)
00213 { children.push_back(new Node(this,misionari-1,kanibalove-1,0,visited | stateBit)); }
00214 }
00215 else if ((lodka == 0) && (misionari < 3) && (kanibalove < 3) && CheckSezrani(misionari+1,kanibalove+1))
00216 {
00217 ulint stateBit = (1 << (((misionari+1) << 3) | ((kanibalove+1) << 1) | 1));
00218
00219 if ((visited & stateBit) == 0)
00220 { children.push_back(new Node(this,misionari+1,kanibalove+1,1,visited | stateBit)); }
00221 }
00222
00223
00224 }
00225
00226 int main()
00227 {
00228 PNode root = new Node();
00229 deque<PNode> fronta;
00230
00231 fronta.push_back(root);
00232
00233 while (fronta.size() > 0)
00234 {
00235 fronta.front()->GenStates();
00236 ulint length = fronta.front()->children.size();
00237
00238 for (ulint i = 0; i < length; i++)
00239 {
00240 fronta.push_back(fronta.front()->children[i]);
00241 }
00242
00243 fronta.pop_front();
00244 }
00245
00246 fronta.push_back(root);
00247
00248 while (fronta.size() > 0)
00249 {
00250 ulint length = fronta.front()->children.size();
00251
00252 if (length == 0)
00253 {
00254 if ((fronta.front()->misionari == 0) && (fronta.front()->kanibalove == 0) && (fronta.front()->lodka == 0))
00255 { fronta.front()->DumpPath(); cout << endl << endl; }
00256 }
00257 else
00258 {
00259 for (ulint i = 0; i < length; i++)
00260 {
00261 fronta.push_back(fronta.front()->children[i]);
00262 }
00263 }
00264
00265 fronta.pop_front();
00266 }
00267
00268 return 1;
00269 }