misionari.cpp

Zobrazit dokumentaci tohoto souboru.
00001 
00039 #include <iostream>
00040 #include <deque>
00041 #include <vector>
00042 using namespace std;
00043 
00044 // forward deklarace Node;
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; } // reseni
00126 
00127                 //OPERATOR 1 : jeden misionar na druhej breh
00128                 //  mame lodku      mame misionare     misionaru bude vic nez kanibalu, nebo nebudou mit co jist
00129                 if ((lodka == 1) && (misionari > 0) && CheckSezrani(misionari-1,kanibalove))
00130                 {
00131                         // misionaru bude o jednoho min, kanibalu stejne, lodka na druhe strane
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                 //      na druhem brehu  je tam misionar    misionaru tam bude vic nez kanibalu, nebo nebudou mit co jist
00138                 else if ((lodka == 0) && (misionari < 3) && CheckSezrani(misionari+1,kanibalove))
00139                 {
00140                         // misionaru bude o jednoho vic, kanibalu bude stejne, lodka tady
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                 //operator 2 - dva misionari na druhej breh
00148                 //  mame lodku      mame misionare     misionaru bude vic nez kanibalu, nebo nebudou mit co jist
00149                 if ((lodka == 1) && (misionari > 1) && CheckSezrani(misionari-2,kanibalove))
00150                 {
00151             // misionaru bude o dva min, kanibalu stejne, lodka na druhe strane
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                 //      na druhem brehu  je tam misionar    misionaru tam bude vic nez kanibalu, nebo nebudou mit co jist
00158                 else if ((lodka == 0) && (misionari < 2) && CheckSezrani(misionari+2,kanibalove))
00159                 {
00160             // misionaru bude o dva vic, kanibalu bude stejne, lodka tady
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                 //operator 3 - jeden kanibal na druhej breh
00168                 //  mame lodku      mame kanibala       misionaru tam bude vic nez kanibalu, nebo nebudou mit co jist
00169                 if ((lodka == 1) && (kanibalove > 0) && CheckSezrani(misionari,kanibalove-1))
00170                 {
00171             // kanibalu bude o jednoho min, misionaru stejne, lodka na druhe strane
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                 //      na druhem brehu  je tam kanibal      misionaru bude vic nez kanibalu, nebo nebudou mit co jist
00178                 else if ((lodka == 0) && (kanibalove < 3) && CheckSezrani(misionari,kanibalove+1))
00179                 {
00180             // kanibalu bude o jednoho vic, misionaru bude stejne, lodka tady
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                 //operator 4 - dva kanibalove na druhej breh
00188                 //  mame lodku      mame kanibala       misionaru tam bude vic nez kanibalu, nebo nebudou mit co jist
00189                 if ((lodka == 1) && (kanibalove > 1) && CheckSezrani(misionari,kanibalove-2))
00190                 {
00191             // kanibalu bude o dva min, misionaru stejne, lodka na druhe strane
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                 //      na druhem brehu  je tam kanibal      misionaru bude vic nez kanibalu, nebo nebudou mit co jist
00198                 else if ((lodka == 0) && (kanibalove < 2) && CheckSezrani(misionari,kanibalove+2))
00199                 {
00200             // kanibalu bude o dva vic, misionaru bude stejne, lodka tady
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                 //operator 5 - misionar a kanibal na druhej breh
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                 //cout << "[" << misionari << "] [" << kanibalove << "] [" << lodka << "] [" << children.size() << "]" << endl;
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 }

Generováno Thu Oct 5 20:35:31 2006 pro projekt Misionari a Kanibalove programem  doxygen 1.4.7