A.First Edition

This is actually first edition of Code Competition 4. (Click to see the problem)

1。 Basic idea: 

This is from last year of "Code Competition" of "Concordia Computer Science Association"(CCSS)

This is a quite unexpected difficult problem as I tried to use "Breadth First Search" which I never tried before.

I finished after more then one day! I guess I won't become the winning team as I think I am not the kind of 

coding fast.

2。 Program design: 

I design a "huge" struct to stand for our nodes. In order to prevent looping, I used the way similar to solution

that is to write a temporary "*" to represent every square I reached. In my old program, I actually record each

step in an array, and I check the contents to see if I am looping. Maybe that is more effiently, I really don't

know. As for find next sibling, I first try to find one of his uncle and then try to see if this uncle has any son

of which the level are same to my current node. Then this should be his "cousin". If there is not a cousin for 

this "uncle", I try to find an "uncle" of this "uncle", then try to find his child of same level of my node. And

so on, if there is no more uncle can be found, this means that there is no cousin. I have to find next generation

of my node by "findFirstSon()" function. Before output result, I erase the temporary mark "*". "Breadth First

Search" will definitely give you the shortest path but it is not the shortest way to code.

3。 Major function：

	A. void startSearch(Node* node)

	This function do the searching job, it tests each node to see if it is exit point. If not, it call addNode()

to add new children of this node. Then it tries to find next node to repeat by first try same generation, if

failed, try next generation.

     B. Node* nextSibling(Node* node)

	This function find next node when constructing my tree. It first find "same father brother", then try find next uncle,if

the uncle has a same-level child, it return the child. If not, try the uncle of "this uncle" until no more uncle fits. It will

try next generation.

     C. Node* findSibling(Node* node)

	This function does what I described above: first find an uncle to see if he has a same-level child. Until no more uncle can

be found, it returns NULL to indicate this.

	D.  Node* findBrother(Node* node)

	This is the function to find same-father brother: if you are left son, the next possible is mid son, or right son by sequence.

If you are mid-son, the only possible is right son. if you are right son, you have no same-father brother.

	E. Node* findFirstSon(Node* node)

	This is a "level-defined" searching for first possible child. Until you reach the level, you will repeat to find the 

first sequence child.

	F. Node* findUncle(Node* node)

	It is simple, your uncle is one of your father's little brother. If you father doesnot have one, try your grandfather.

	G. void addNode(Node* node)

	Node* doAdding(Node* node, Direction dir);

	This function generate sons of this node with directions which means that according to the node's direction, you arrange

the sequence of left, mid, right son accordingly. He has an internal function doAdding();

	H. bool solveMaze(FILE* stream)

	   void initialize();

	Pls note the internal method initialize() which has to clear all nodes before we can re-construct the tree. However, this

means a "Walk-Arround" from all leafs of tree to delete one by one. Its internal function "findSingle()" is similar as

findFirstSon() except it doesnot require to go to certain depth levels.

4。 Further improvement：

	A. I use too many recursive calls which may require too much memory.	

	B. I forgot to delete all tree when program ended.

#include <iostream>
#include <fstream>

using namespace std;

enum Direction
{Up, Right, Down, Left};

const Space = 32;

const Wall = 'X';

const Passed = '*';

const Route = '.';

const Return = '\n';

const MaxRow = 20;

const MaxCol = 70;

const MaxStep = 200;

char maze[MaxRow][MaxCol];

struct Node
{
	Node* parent;
	Node* left;
	Node* mid;
	Node* right;
	int row;
	int col;
	Direction direction;
	int level;
};

Node start;

int level =0;

int rowLimit = 0;

int colLimit = 0;

bool solveMaze(FILE* stream);

bool inputFile(char* fileName);

void outputFile(char* fileName);

bool evalueNode(Node* node);

void generateNode(Node* node);

void startSearch(Node* node);

Node* findSibling(Node* node);

void recordPath(Node* node);

Node* findUncle(Node* node);

Node* findFirstSon(Node* node);

Node* findBrother(Node* node);

Node* nextNephew();

void addPath(Node* node);

int main()
{
	FILE* f;
	f = fopen("c:\\nickinput.txt", "r");
	while (solveMaze(f))
	{
		outputFile("c:\\nickoutput.txt");
	}
	return 0;
}

void outputFile(char* fileName)
{
	FILE*  stream;
	stream = fopen(fileName, "a");
	for (int i = 0; i< rowLimit; i++)
	{
		for (int j =0; j < colLimit; j++)
		{
			if (maze[i][j] == Passed)
			{
				maze[i][j] = Space;
			}
			fputc(maze[i][j], stream);
		}
		fputc('\n', stream);
	}
	fclose(stream);
}

Node* findSingle(Node* node)
{
	Node* ptr= node;
	if (node != NULL)
	{
		ptr = findSingle(node->left);
		if (ptr==NULL)
		{
			ptr = findSingle(node->mid);
		}
		if (ptr==NULL)
		{
			ptr = findSingle(node->right);
		}
		if (ptr==NULL)
		{
			ptr = node;
		}
	}
	return ptr;
}

void destroy(Node* ptr)
{
	if (ptr->parent->left == ptr)
	{
		ptr->parent->left = NULL;
	}
	if (ptr->parent->mid == ptr)
	{
		ptr->parent->mid = NULL;
	}
	if (ptr->parent->right == ptr)
	{
		ptr->parent->right = NULL;
	}
	delete ptr;
}

void initialize()
{
	Node* findSingle(Node* node);
	void destroy(Node* ptr);

	Node* ptr = &start;
	while (true)
	{
		ptr = &start;
		ptr = findSingle(ptr);
		if (ptr!=&start&&ptr!=NULL)
		{
			destroy(ptr);			
		}
		else
		{
			break;
		}
	}
	level =0;
	colLimit = 0;
	rowLimit = 0;
	start.row = 0;
	start.col = 0;
	start.left = NULL;
	start.mid  = NULL;
	start.right = NULL;
	start.parent = NULL;
	start.level = 0;
}

bool solveMaze(FILE* stream)
{
	void initialize();
	char ch;
	Node* ptr = &start;
	bool setRoot = false;
	int i=0, j=0;
	

	initialize();

	ch = fgetc(stream);
	while(true)
	{
		j =0;
		while(ch!=Return)
		{
			maze[i][j] = ch;
			ch = fgetc(stream);
			j++;
		}
		i++;
		if (i ==1)
		{
			if (j==1)
			{
				return false;
			}
			colLimit = j;
		}
	

		ch = fgetc(stream);
		if (ch==Return)
		{
			rowLimit = i;
			break;
		}
	

		if (ch == Space&&!setRoot)
		{
			start.row = i;
			start.col = 0;
			setRoot = true;
			start.left = NULL;
			start.mid =NULL;
			start.right = NULL;
			start.parent = NULL;
			start.direction = Right;
			start.level = 0;
			maze[i][0] = Passed;
		}
	

	}
	startSearch(ptr);
	return true;
	

}

Node* doAdding(Node* node, Direction dir)
{
	int row, col;
	Node* ptr;

	row = node->row;
	col = node->col;

	switch (dir)
	{
	case Up:
		row--;
		break;
	case Right:
		col++;
		break;
	case Down:
		row++;
		break;
	case Left:
		col--;
		break;
	}
	if (row<0||row>=rowLimit||col<0||col>=colLimit||maze[row][col]==Passed
		||maze[row][col]==Wall)
	{
		return NULL;
	}
	ptr = new Node;
	ptr->row = row;
	ptr->col = col;
	ptr->direction = dir;
	ptr->parent = node;
	ptr->left = NULL;
	ptr->mid = NULL;
	ptr->right = NULL;
	ptr->level = node->level + 1;
	maze[row][col] = Passed;
	return ptr;
}

void addNode(Node* node)
{
	Node* doAdding(Node* node, Direction dir);

	maze[node->row][node->col] = Passed;
	switch (node->direction)
	{
	case Up:
		node->left = doAdding(node, Left);
		node->mid = doAdding(node, Up);
		node->right = doAdding(node, Right);
		break;
	case Right:
		node->left = doAdding(node, Up);
		node->mid = doAdding(node, Right);
		node->right = doAdding(node, Down);
		break;
	case Down:
		node->left = doAdding(node, Right);
		node->mid = doAdding(node, Down);
		node->right = doAdding(node, Left);
		break;
	case Left:
		node->left = doAdding(node, Down);
		node->mid = doAdding(node, Left);
		node->right = doAdding(node, Up);
		break;
	}
			

}

bool testNode(Node* node)
{
	if (node!=&start&&node->col == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

Node* findUncle(Node* node)
{
	Node* ptr = node;
	if (ptr->parent!=NULL)
	{
		ptr = findBrother(ptr->parent);
		if (ptr!=NULL)
		{
			return ptr;
		}
		else
		{
			return findUncle(node->parent);
		}
	}
	return NULL;
}

Node* findFirstSon(Node* node)
{
	Node* ptr = node;
	if (ptr==NULL)
	{
		return NULL;
	}
	if (ptr->level != level)
	{
		ptr = findFirstSon(node->left);
		if (ptr==NULL)
		{
			ptr = findFirstSon(node->mid);
		}
		if (ptr==NULL)
		{
			ptr = findFirstSon(node->right);
		}
		

	}
	return ptr;
}

Node* findBrother(Node* node)
{
	Node* ptr= NULL;
	if (node!= NULL)
	{
		if (node->parent==NULL)
		{
			return NULL;
		}

		if (node->parent->left==node)
		{
			ptr = node->parent->mid;  //problem
			if (ptr==NULL)
			{
				ptr = node->parent->right;
			}
		}
		if (node->parent->mid == node)
		{
			ptr = node->parent->right;
		}
		return ptr;
	}
	return NULL;
}

Node* findSibling(Node* node)
{
	Node* pUncle = node;
	Node* ptr;

	while (true)
	{
		pUncle = findUncle(pUncle);
		if (pUncle ==NULL)
		{
			return NULL;
		}
		ptr = findFirstSon(pUncle);
		if (ptr!= NULL)
		{
			return ptr;
		}
	}	
}

Node* nextSibling(Node* node)
{
	Node* ptr = node;
	ptr = findBrother(node);
	if (ptr==NULL)
	{
		ptr = findSibling(node);
	}
	return ptr;
}

	
Node* nextNephew()
{
	level++;
	return findFirstSon(&start);
}

void addPath(Node* node)
{
	maze[node->row][node->col] = Route;
	if (node->level == 0)
	{
		return;
	}
	else
	{
		addPath(node->parent);
	}
}

void startSearch(Node* node)
{
	Node* ptr;
	Node* pNode;
		

	pNode = node;
	while (!testNode(pNode))
	{
		addNode(pNode);
		ptr = nextSibling(pNode);
		if (ptr==NULL)
		{
			ptr = nextNephew();
			if (ptr==NULL)
			{
				cout<<"no solution!";
				//return;
			}
		}
		pNode = ptr;
	}

	addPath(pNode);
}

XXXXXXXX
XX     X
   X XXX
XXX  X X
       X 
XXXXXXXX

XXXXXXXXXX
X        X 
  XX XXXXX
XX       X
  XXXXXX X
X        X
XXXXXXXXXX

X

XXXXXXXX
XX...  X
...X.XXX
XXX .X X
.....  X
XXXXXXXX
XXXXXXXXXX
X....    X
..XX.XXXXX
XX  .....X
..XXXXXX.X
X........X
XXXXXXXXXX

Hosted by www.Geocities.ws