Count Number--Application of BFS
A.First Edition
This is actually another application of my BFS class, or you can call it third edition of counting model, whatever.
The base framework are exactly same as Counting problem except that I standardize my BFS class. I made it similar
to my DFS class. Now programmer need only to overload the several functions and the BFS can do the job.
A string that contains 0s,1s and 2s is called a ternary string. Find the number of ternary strings that contain
no consecutive 0s.(The original problem is to find string that DOES contain consecutive 0s. But it is almost same
question as you can find it by using 3^n to minus it. Understand?)
No matter how complicated a problem may become, we can divide and conquer it by counting! And breadth-first-search
is one of the simplest way to do it.
1. void BFS::beginCount(int max)
I add a parameter for this major function. The parameter max means to set up the maximum searching depth so that
you can control the outcome. (Try to recall that I have more than 4million nodes at level 11.)
2. void BFS::setOptionArray(int *array, int arraySize)
This is another function that user need to call. It passes the user-defined options----an int array, and its size.
3. bool BFS::validateOption(int sonData)
This remains almost no change as previous edition. Programmer need to specify their own condition for each option.
4. void BFS::onVisit() void BFS::assignString(char** nameString)
I change the function onVisit() to make it a standard display method. And programmer can only pass in their display
string by method assignString(). So, the display method is standardized.
กก
#include <iostream>
using namespace std;
const int MaxSonCount =8;
const int MaxLevel = 20;
const int MaxOptionCount = 10;
enum BitName
{Zero, One, Two};
char* BitString[3] = {"0", "1", "2"};
int bitOption[3] = {Zero, One, Two};
class BFS
{
private:
static BFS root;
static int level;
static int optionArray[MaxOptionCount];
static int optionCount;
static int maxLevel;
int depth;
BFS* parent;
BFS* sonArray[MaxSonCount];
int data;
int sonCount;
int sonIndex;
void addSon(int sonData);
BFS* findBrother();
BFS* findUncle();
bool hasBrother();
BFS* nextBrother();
BFS* diving();
void initialize();
bool touchDown();
bool canDive();
bool generate();
void traverse();
void setMaxLevel(int max) { maxLevel = max;}
void assignString(char** nameString);
protected:
virtual bool lastChance();
virtual void doGenerate();
virtual bool validateOption(int sonData);
virtual void onVisit();
public:
void setOptionArray(int* array, int arraySize);
void beginCount(int max);
};
int BFS::level = 0;
BFS BFS::root;
int BFS::optionArray[MaxOptionCount] = {0};
int BFS::optionCount = 0;
int BFS::maxLevel = 0;
int main()
{
BFS R;
R.setOptionArray(bitOption, 3);
R.beginCount(4);
return 0;
}
void BFS::setOptionArray(int *array, int arraySize)
{
optionCount = arraySize;
for (int i=0; i< optionCount; i++)
{
optionArray[i] = array[i];
}
}
void BFS::assignString(char** nameString)
{
int temp[MaxLevel] = {0};
BFS* ptr = this;
while (ptr->parent!=NULL)
{
temp[ptr->depth-1] = ptr->data;
ptr = ptr->parent;
}
cout<<" The route is:";
for (int i=0; i<depth; i++)//depth is one more than level!!!!!!
{
cout<<nameString[temp[i]]<<", ";
}
cout<<endl;
}
void BFS::onVisit()
{
assignString(BitString);
}
bool BFS::validateOption(int sonData)
{
if (sonData==Zero)
{
if (parent!=NULL)
{
if (data==Zero)
{
return false;
}
}
}
return true;
}
void BFS::doGenerate()
{
for (int i=0; i<optionCount; i++)
{
if (validateOption(optionArray[i]))
{
addSon(optionArray[i]);
}
}
}
bool BFS::lastChance()
{
return level==maxLevel-1;
}
void BFS::traverse()
{
int counter=0;
BFS* ptr= &root;
while (ptr!=NULL)
{
while(ptr->canDive())
{
ptr= ptr->sonArray[0];
}
cout<<"now it is:"<<++counter;
ptr->onVisit();
if (ptr->hasBrother())
{
ptr= ptr->nextBrother();
}
else
{
ptr=ptr->findUncle();
}
}
cout<<"The total number is :"<<counter<<endl;
}
void BFS::beginCount(int max)
{
setMaxLevel(max);
initialize();
while (generate())
{
if (!lastChance()) //true to keep go on
{
level++;
cout<<"Now is level:"<<level<<endl;
}
else
{
break;
}
}
traverse();
}
bool BFS::generate()
{
BFS* ptr= this;
ptr = root.diving();
if (ptr==NULL)
{
return false;
}
while (ptr!=NULL)
{
ptr->doGenerate();
ptr = ptr->findBrother();
}
return true;
}
bool BFS::touchDown()
{
return depth ==level;
}
bool BFS::canDive()
{
return sonCount>0;
}
void BFS::initialize()
{
root.depth = 0;
root.sonCount = 0;
root.sonIndex = -1;
root.parent = NULL;
root.data = 0;
level = 0;
}
//NULL only when there is no more brother
BFS* BFS::diving()
{
BFS* ptr = this;
while (!ptr->touchDown())
{
if (ptr->canDive())
{
ptr = ptr->sonArray[0];
}
else
{
if (ptr->hasBrother())
{
ptr = ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
}
}
if (ptr==NULL)
{
break; //no more way to dive
}
}
return ptr;
}
bool BFS::hasBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return true;
}
}
return false;
}
BFS* BFS::nextBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return parent->sonArray[sonIndex+1]; //next little brother
}
}
return NULL;
}
BFS* BFS::findUncle()
{
BFS* ptr= this;
while (!(ptr->hasBrother()))
{
ptr = ptr->parent;
if (ptr==NULL)
{
return NULL;
}
}
return ptr->nextBrother();
}
BFS* BFS::findBrother()
{
BFS* ptr = this;
if (ptr->hasBrother())
{
return ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
if (ptr==NULL)
{
return NULL;
}
else
{
return ptr->diving();
}
}
}
void BFS::addSon(int sonData)
{
if (sonCount+1<MaxSonCount)
{
BFS* ptr = new BFS;
ptr->data = sonData;
ptr->sonCount = 0;
ptr->parent = this;
ptr->depth = level+1;
sonArray[sonCount] = ptr;
ptr->sonIndex = sonCount;
sonCount++;
}
else
{
cout<<"Exceed max of sons!";
}
}
The following is result of program: (the result is too much even with reduced searching levels)
now it is:1 The route is:0, 1, 0, 1, 0, now it is:2 The route is:0, 1, 0, 1, 1, now it is:3 The route is:0, 1, 0, 1, 2, now it is:4 The route is:0, 1, 0, 2, 0, now it is:5 The route is:0, 1, 0, 2, 1, now it is:6 The route is:0, 1, 0, 2, 2, now it is:7 The route is:0, 1, 1, 0, 1, now it is:8 The route is:0, 1, 1, 0, 2, now it is:9 The route is:0, 1, 1, 1, 0, now it is:10 The route is:0, 1, 1, 1, 1, now it is:11 The route is:0, 1, 1, 1, 2, now it is:12 The route is:0, 1, 1, 2, 0, now it is:13 The route is:0, 1, 1, 2, 1, now it is:14 The route is:0, 1, 1, 2, 2, now it is:15 The route is:0, 1, 2, 0, 1, now it is:16 The route is:0, 1, 2, 0, 2, now it is:17 The route is:0, 1, 2, 1, 0, now it is:18 The route is:0, 1, 2, 1, 1, now it is:19 The route is:0, 1, 2, 1, 2, now it is:20 The route is:0, 1, 2, 2, 0, now it is:21 The route is:0, 1, 2, 2, 1, now it is:22 The route is:0, 1, 2, 2, 2, now it is:23 The route is:0, 2, 0, 1, 0, now it is:24 The route is:0, 2, 0, 1, 1, now it is:25 The route is:0, 2, 0, 1, 2, now it is:26 The route is:0, 2, 0, 2, 0, now it is:27 The route is:0, 2, 0, 2, 1, now it is:28 The route is:0, 2, 0, 2, 2, now it is:29 The route is:0, 2, 1, 0, 1, now it is:30 The route is:0, 2, 1, 0, 2, now it is:31 The route is:0, 2, 1, 1, 0, now it is:32 The route is:0, 2, 1, 1, 1, now it is:33 The route is:0, 2, 1, 1, 2, now it is:34 The route is:0, 2, 1, 2, 0, now it is:35 The route is:0, 2, 1, 2, 1, now it is:36 The route is:0, 2, 1, 2, 2, now it is:37 The route is:0, 2, 2, 0, 1, now it is:38 The route is:0, 2, 2, 0, 2, now it is:39 The route is:0, 2, 2, 1, 0, now it is:40 The route is:0, 2, 2, 1, 1, now it is:41 The route is:0, 2, 2, 1, 2, now it is:42 The route is:0, 2, 2, 2, 0, now it is:43 The route is:0, 2, 2, 2, 1, now it is:44 The route is:0, 2, 2, 2, 2, now it is:45 The route is:1, 0, 1, 0, 1, now it is:46 The route is:1, 0, 1, 0, 2, now it is:47 The route is:1, 0, 1, 1, 0, now it is:48 The route is:1, 0, 1, 1, 1, now it is:49 The route is:1, 0, 1, 1, 2, now it is:50 The route is:1, 0, 1, 2, 0, now it is:51 The route is:1, 0, 1, 2, 1, now it is:52 The route is:1, 0, 1, 2, 2, now it is:53 The route is:1, 0, 2, 0, 1, now it is:54 The route is:1, 0, 2, 0, 2, now it is:55 The route is:1, 0, 2, 1, 0, now it is:56 The route is:1, 0, 2, 1, 1, now it is:57 The route is:1, 0, 2, 1, 2, now it is:58 The route is:1, 0, 2, 2, 0, now it is:59 The route is:1, 0, 2, 2, 1, now it is:60 The route is:1, 0, 2, 2, 2, now it is:61 The route is:1, 1, 0, 1, 0, now it is:62 The route is:1, 1, 0, 1, 1, now it is:63 The route is:1, 1, 0, 1, 2, now it is:64 The route is:1, 1, 0, 2, 0, now it is:65 The route is:1, 1, 0, 2, 1, now it is:66 The route is:1, 1, 0, 2, 2, now it is:67 The route is:1, 1, 1, 0, 1, now it is:68 The route is:1, 1, 1, 0, 2, now it is:69 The route is:1, 1, 1, 1, 0, now it is:70 The route is:1, 1, 1, 1, 1, now it is:71 The route is:1, 1, 1, 1, 2, now it is:72 The route is:1, 1, 1, 2, 0, now it is:73 The route is:1, 1, 1, 2, 1, now it is:74 The route is:1, 1, 1, 2, 2, now it is:75 The route is:1, 1, 2, 0, 1, now it is:76 The route is:1, 1, 2, 0, 2, now it is:77 The route is:1, 1, 2, 1, 0, now it is:78 The route is:1, 1, 2, 1, 1, now it is:79 The route is:1, 1, 2, 1, 2, now it is:80 The route is:1, 1, 2, 2, 0, now it is:81 The route is:1, 1, 2, 2, 1, now it is:82 The route is:1, 1, 2, 2, 2, now it is:83 The route is:1, 2, 0, 1, 0, now it is:84 The route is:1, 2, 0, 1, 1, now it is:85 The route is:1, 2, 0, 1, 2, now it is:86 The route is:1, 2, 0, 2, 0, now it is:87 The route is:1, 2, 0, 2, 1, now it is:88 The route is:1, 2, 0, 2, 2, now it is:89 The route is:1, 2, 1, 0, 1, now it is:90 The route is:1, 2, 1, 0, 2, now it is:91 The route is:1, 2, 1, 1, 0, now it is:92 The route is:1, 2, 1, 1, 1, now it is:93 The route is:1, 2, 1, 1, 2, now it is:94 The route is:1, 2, 1, 2, 0, now it is:95 The route is:1, 2, 1, 2, 1, now it is:96 The route is:1, 2, 1, 2, 2, now it is:97 The route is:1, 2, 2, 0, 1, now it is:98 The route is:1, 2, 2, 0, 2, now it is:99 The route is:1, 2, 2, 1, 0, now it is:100 The route is:1, 2, 2, 1, 1, now it is:101 The route is:1, 2, 2, 1, 2, now it is:102 The route is:1, 2, 2, 2, 0, now it is:103 The route is:1, 2, 2, 2, 1, now it is:104 The route is:1, 2, 2, 2, 2, now it is:105 The route is:2, 0, 1, 0, 1, now it is:106 The route is:2, 0, 1, 0, 2, now it is:107 The route is:2, 0, 1, 1, 0, now it is:108 The route is:2, 0, 1, 1, 1, now it is:109 The route is:2, 0, 1, 1, 2, now it is:110 The route is:2, 0, 1, 2, 0, now it is:111 The route is:2, 0, 1, 2, 1, now it is:112 The route is:2, 0, 1, 2, 2, now it is:113 The route is:2, 0, 2, 0, 1, now it is:114 The route is:2, 0, 2, 0, 2, now it is:115 The route is:2, 0, 2, 1, 0, now it is:116 The route is:2, 0, 2, 1, 1, now it is:117 The route is:2, 0, 2, 1, 2, now it is:118 The route is:2, 0, 2, 2, 0, now it is:119 The route is:2, 0, 2, 2, 1, now it is:120 The route is:2, 0, 2, 2, 2, now it is:121 The route is:2, 1, 0, 1, 0, now it is:122 The route is:2, 1, 0, 1, 1, now it is:123 The route is:2, 1, 0, 1, 2, now it is:124 The route is:2, 1, 0, 2, 0, now it is:125 The route is:2, 1, 0, 2, 1, now it is:126 The route is:2, 1, 0, 2, 2, now it is:127 The route is:2, 1, 1, 0, 1, now it is:128 The route is:2, 1, 1, 0, 2, now it is:129 The route is:2, 1, 1, 1, 0, now it is:130 The route is:2, 1, 1, 1, 1, now it is:131 The route is:2, 1, 1, 1, 2, now it is:132 The route is:2, 1, 1, 2, 0, now it is:133 The route is:2, 1, 1, 2, 1, now it is:134 The route is:2, 1, 1, 2, 2, now it is:135 The route is:2, 1, 2, 0, 1, now it is:136 The route is:2, 1, 2, 0, 2, now it is:137 The route is:2, 1, 2, 1, 0, now it is:138 The route is:2, 1, 2, 1, 1, now it is:139 The route is:2, 1, 2, 1, 2, now it is:140 The route is:2, 1, 2, 2, 0, now it is:141 The route is:2, 1, 2, 2, 1, now it is:142 The route is:2, 1, 2, 2, 2, now it is:143 The route is:2, 2, 0, 1, 0, now it is:144 The route is:2, 2, 0, 1, 1, now it is:145 The route is:2, 2, 0, 1, 2, now it is:146 The route is:2, 2, 0, 2, 0, now it is:147 The route is:2, 2, 0, 2, 1, now it is:148 The route is:2, 2, 0, 2, 2, now it is:149 The route is:2, 2, 1, 0, 1, now it is:150 The route is:2, 2, 1, 0, 2, now it is:151 The route is:2, 2, 1, 1, 0, now it is:152 The route is:2, 2, 1, 1, 1, now it is:153 The route is:2, 2, 1, 1, 2, now it is:154 The route is:2, 2, 1, 2, 0, now it is:155 The route is:2, 2, 1, 2, 1, now it is:156 The route is:2, 2, 1, 2, 2, now it is:157 The route is:2, 2, 2, 0, 1, now it is:158 The route is:2, 2, 2, 0, 2, now it is:159 The route is:2, 2, 2, 1, 0, now it is:160 The route is:2, 2, 2, 1, 1, now it is:161 The route is:2, 2, 2, 1, 2, now it is:162 The route is:2, 2, 2, 2, 0, now it is:163 The route is:2, 2, 2, 2, 1, now it is:164 The route is:2, 2, 2, 2, 2, The total number is :164 Press any key to continue
กก