3_MazePathScore.cpp

#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

struct PathQueueNode
{
	int RowIndex;
	int ColIndex;
	PathQueueNode* Next;
};

struct StackNode
{
	int RowIndex;
	int ColIndex;
	StackNode* next;
	
	PathQueueNode* SavedPathLastQPointer;
};

void GetMaze(char**, int, int);
bool CheckMaze(char**, int, int);
void PrintMaze(char**, int, int);
void ProcessMaze(char**, int , int);
void PushToStack(int, int, PathQueueNode*);
bool PopFromStack(int &, int &, PathQueueNode* &, char**); 
void EnqueuePath(int, int);
void Dequeue(char**, int[], int);
void CopyMaze(char**, char**, int, int);
void DeleteMazeCopy(char**, int);


StackNode* TopPointer = NULL;
PathQueueNode* PathStartQPointer = NULL;
PathQueueNode* PathLastQPointer = NULL;


int main(int argc, char** argv)
{	
	char** Maze = NULL;
	int iMaxRows, iMaxCols;
	
	cout << "Enter the number of rows in the maze." << endl;
	cin >> iMaxRows;
	
	cout << "Enter the number of columns in the maze." << endl;
	cin >> iMaxCols;
	
	Maze = new char*[iMaxRows];
	for (int i = 0; i < iMaxRows; i++)
	{
		Maze[i] = new char[iMaxCols];
	}
	
	GetMaze(Maze, iMaxRows, iMaxCols);
	
	bool IsMazeCorrect = CheckMaze(Maze, iMaxRows, iMaxCols);
	while (!IsMazeCorrect)
	{
		cout << "Maze Entered is Invalid." << endl;
		cout << "Please enter it again." << endl;
		GetMaze(Maze, iMaxRows, iMaxCols);
		IsMazeCorrect = CheckMaze(Maze, iMaxRows, iMaxCols);
	}
	
	PrintMaze(Maze, iMaxRows, iMaxCols);
	
	ProcessMaze(Maze, iMaxRows, iMaxCols);
	
	// TODO: Delete Contents of Stack, if any, using TopPointer.
	
	// TODO: Delete Contents of List, using PathStartQPointer.
	
	system("pause");
	return 0;
}

void GetMaze(char** Maze, int iMaxRows, int iMaxCols)
{
	char ch;
	
	cout << "Enter the contents of the Maze." << endl;
	cout << "S indicates the Start of the Maze ." << endl;
	cout << "E indicates the End of the Maze." << endl;
	cout << "0 indicates the cell you can go on." << endl;
	cout << "1 indicates the cell you cannot go on." << endl << endl;
	
	int i = 0;
	int j = 0;
	while (cin.get(ch))
	{
		if (ch == EOF)
		   break;
		   
		if ((ch == '\n') || (ch == ' '))   
		   continue;
		
		Maze[i][j] = ch;
		
		j++;
		
		if (j > (iMaxCols-1)) // Max Possible Value for j is (iMaxCols-1)
		{
		   i++;
		   j = 0;
        }
		
		if (i > (iMaxRows-1) ) // Max Possible Value for i is (iMaxRows-1)
		  break;      
	}
}

bool CheckMaze(char** Maze, int iMaxRows, int iMaxCols)
{
	int StartCount = 0;
	int EndCount = 0;
	for (int i = 0; i < iMaxRows; i++)
	{
		for (int j = 0; j < iMaxCols; j++)
		{
			if (!((Maze[i][j] == '0') || (Maze[i][j] == '1') || (Maze[i][j] == 'S') || (Maze[i][j] == 'E')))
			{
				cout << "Character entered in the maze is invalid." << endl;
				return false;
			}
			else if (Maze[i][j] == 'S')
			{
				StartCount++;
			}
			else if (Maze[i][j] == 'E')
			{
				EndCount++;
			}
		}
	}
	
	if (StartCount != 1)
	{
		if (StartCount == 0)
		{
			cout << "There is no entry point in the maze " << endl;
			return false;
		}
		else
		{
			cout << "There cannot be more than one entry point in the maze" << endl;
			return false;
		}
	}
	
    if (EndCount != 1)
	{
		if (EndCount == 0)
		{
			cout << "There is no exit point in the maze " << endl;
			return false;
		}
		else
		{
			cout << "There cannot be more than one exit point in the maze" << endl;
			return false;
		}
	}
	
	return true;
}

void PrintMaze(char** Maze, int iMaxRows, int iMaxCols)
{
	cout << endl;
	
	for (int i = 0; i < iMaxRows ; i++)
	{
		for (int j = 0; j < iMaxCols; j++)
		{
			cout << setw(2) << Maze[i][j] ;
		}
		cout << endl;
	}
}

void ProcessMaze(char** Maze, int iMaxRows, int iMaxCols)
{
	int i=-1, j=-1;
	for (i = 0; i < iMaxRows; i++)
	{
		for (j = 0; j < iMaxCols; j++)
		{
			if (Maze[i][j] == 'S')
			{
			    break;	
			}
		}
		
		if (Maze[i][j] == 'S')
		{
		    break;	
		}	
	}
	
	if ((i == -1) || (j == -1))
	   return;
	
	PathQueueNode* NewQNode = new PathQueueNode;;
	NewQNode->RowIndex = i;
	NewQNode->ColIndex = j;
	NewQNode->Next = NULL;
	PathStartQPointer = NewQNode; 
	PathLastQPointer =  NewQNode;
	 
	int PathScore[100000]; 
	int PathScoreIndex = 0;
	int NoOfExits = 0;
	 
	bool bKeepGoing = true;
	while (bKeepGoing)
	{	 
		if (Maze[i][j] == 'E')
		{
			NoOfExits++;
			
			cout << endl;
			//cout << "Exit found at " << "Row: " << i << " Col: " << j << endl;
			//cout << "Path of the maze is along:" << endl;
			
			char** MazeCopy = new char*[iMaxRows];
			for (int l = 0; l < iMaxRows; l++)
			{
				MazeCopy[l] = new char[iMaxCols];
			}
			
			CopyMaze(Maze, MazeCopy, iMaxRows, iMaxCols);
			
			PathScore[PathScoreIndex] = 0;
			
			Dequeue(MazeCopy, PathScore, PathScoreIndex); // This will change values in the path to '*'
			
			//cout << endl << "After Reaching Exit: Maze is as follows: " << endl;
			//PrintMaze(Maze, iMaxRows, iMaxCols);
			
			//cout << "Row = " << i << " Col = " << j << endl;  //Printing indices of Exit. 
			
			for (int m = 0; m < iMaxRows; m++)
			{
				for (int n = 0; n < iMaxCols; n++)
				{
					cout << setw(2) << MazeCopy[m][n];
				}
				cout << endl;
			}
			
			cout << "Score of the Path = " << PathScore[PathScoreIndex] << endl;
			
			DeleteMazeCopy(MazeCopy, iMaxRows);
			
			PathScoreIndex++;
			
			if (! PopFromStack(i, j, PathLastQPointer, Maze) ) 
			{
				break;
		    }  
		    
			//cout << endl << "Before Reaching Exit: Maze is as follows: " << endl;
			//PrintMaze(Maze, iMaxRows, iMaxCols);		
		}
		
	    // Visiting (i,j) 
		if ((Maze[i][j] != 'S') && (Maze[i][j] != 'E') && (Maze[i][j] != '1') )
		{
			// Never change a Pushed Node to Visited Node UNLESS it is popped.
			// Actually, we never traverse to a Pushed Node. We will only come there via a Pop. Then its ok to change 'P' to 'V'
			// if (Maze[i][j] != 'P') // NOT REQURIED
			   // Maze[i][j] = 'V'; // SETTING TO V IS VERY IMPORTANT TO AVOID GOING IN CIRCLES, FOR A GIVEN PATH FROM 'S' TO 'E'. These V's should be set to ZERO at start of finding another alternative path.

            Maze[i][j] = 'V'; // SETTING TO V IS VERY IMPORTANT TO AVOID GOING IN CIRCLES, FOR A GIVEN PATH FROM 'S' TO 'E'. These V's should be set to ZERO at start of finding another alternative path.
			EnqueuePath(i, j);
		}
				
		bool bTopOK = false; 
		bool bBottomOK = false; 
		bool bLeftOK = false;
		bool bRightOK = false;
		
		// BugFix 2: 
		// Analyzing a Node can result in its Neighbouring Node and Pushed to Stack.
		// Then the Pushed Node can be a neighbour of another Node that is being Analyzed.
		// This represents an alternative unique path that traverses a pushed node.
		// So in order to cover the alternative path, the node has to be pushed again.
		// Whenever a node is pushed, the current is also pushed along with it.
		// Here, even though the same node means (i, j), is pushed more than once, each push
		// will have a different path associated with the pushed node.
		// This bug was fixed below by adding the OR clause to include 'P' pushed nodes.
		// The below flags are set, which mean, that we can move to a node which is already pushed
		// OR the node can be pushed again.
		if ( (i >= 1) && ((Maze[i-1][j] == '0') || (Maze[i-1][j] == 'P')) ) 
		{
			bTopOK = true;
	    } 
	    
	    if ( (i < (iMaxRows - 1)) && ((Maze[i+1][j] == '0') || (Maze[i+1][j] == 'P')) ) 
	    {
	    	bBottomOK = true;
		}
		
		if ( (j >= 1) && ((Maze[i][j-1] == '0') || (Maze[i][j-1] == 'P')) ) 
		{
			bLeftOK = true;
		}
		
		if ( (j < (iMaxCols - 1)) && ((Maze[i][j+1] == '0') || (Maze[i][j+1] == 'P')) ) 
		{
			bRightOK = true;
		}
		
		// If neighbouring node is 'E', then it is necessary to analyze the others neighbours & push, before going to E.
		// BugFix 1: 
		// When one of the neighbours is the Exit node, we were not analyzing the other neighbours for pushing to stack.
		// This caused several paths to be missed out.
		// This was fixed by adding the 3 if statements in each if block below and call to push to stack.
		if ((i >= 1) && (Maze[i-1][j] == 'E'))
		{
			if (bRightOK)
			{
				Maze[i][j+1] = 'P';
				PushToStack(i, j+1, PathLastQPointer);
			}
			if (bLeftOK)
			{
				Maze[i][j-1] = 'P';
				PushToStack(i, j-1, PathLastQPointer);  
			}
			if (bBottomOK)
			{
				Maze[i+1][j] = 'P';
				PushToStack(i+1, j, PathLastQPointer);
			}
				
			i = i-1;
			j = j;		
			continue;
		}	
		else if ((i < (iMaxRows - 1)) && (Maze[i+1][j] == 'E'))
		{
			if (bRightOK)
			{
				Maze[i][j+1] = 'P';
				PushToStack(i, j+1, PathLastQPointer);
			}
			if (bLeftOK)
			{
				Maze[i][j-1] = 'P';
				PushToStack(i, j-1, PathLastQPointer);
			}
			if (bTopOK)
			{
				Maze[i-1][j] = 'P';
				PushToStack(i-1, j, PathLastQPointer);       
			}			
			
			i = i+1;
			j = j;		
			continue;
		}	
		else if ((j >= 1) && (Maze[i][j-1] == 'E'))
		{
			if (bRightOK)
			{
				Maze[i][j+1] = 'P';
				PushToStack(i, j+1, PathLastQPointer);   
			}
			if (bBottomOK)
			{
				Maze[i+1][j] = 'P';
				PushToStack(i+1, j, PathLastQPointer);  
			}
			if (bTopOK)
			{
				Maze[i-1][j] = 'P';
				PushToStack(i-1, j, PathLastQPointer);
			}			
			
			i = i;
			j = j-1;		
			continue;
		}
		else if ((j < (iMaxCols - 1)) && (Maze[i][j+1] == 'E'))
		{
			if (bLeftOK)
			{
				Maze[i][j-1] = 'P';
				PushToStack(i, j-1, PathLastQPointer);	    
			}
			if (bBottomOK)
			{
				Maze[i+1][j] = 'P';
				PushToStack(i+1, j, PathLastQPointer); 
			}
			if (bTopOK)
			{
				Maze[i-1][j] = 'P';
				PushToStack(i-1, j, PathLastQPointer);	    
			}
			
			i = i;
			j = j+1;		
			continue;
		}
			
		// The below three variables is set when you Pop from the Stack. The values were originally pushed to the Stack and 
		// later read into the below three variables.
	    int	 newi = -1;
        int	 newj = -1;
		PathQueueNode* newPathLastQPointer = NULL;
		
		if (bTopOK) 
		{
			newi = i-1;
			newj = j;
			
			if (bRightOK)
			{
				Maze[i][j+1] = 'P';
				PushToStack(i, j+1, PathLastQPointer);
			}
			if (bLeftOK)
			{
				Maze[i][j-1] = 'P';
				PushToStack(i, j-1, PathLastQPointer);  
			}
			if (bBottomOK)
			{
				Maze[i+1][j] = 'P';
				PushToStack(i+1, j, PathLastQPointer);
			}
		}
		else if (bBottomOK)
		{
			newi = i+1;
			newj = j;
			
			if (bRightOK)
			{
				Maze[i][j+1] = 'P';
				PushToStack(i, j+1, PathLastQPointer);
			}
			if (bLeftOK)
			{
				Maze[i][j-1] = 'P';
				PushToStack(i, j-1, PathLastQPointer);
			}
			if (bTopOK)
			{
				Maze[i-1][j] = 'P';
				PushToStack(i-1, j, PathLastQPointer);       
			}
		}
		else if (bLeftOK)
		{
			newi = i;
			newj = j-1;
			
			if (bRightOK)
			{
				Maze[i][j+1] = 'P';
				PushToStack(i, j+1, PathLastQPointer);   
			}
			if (bBottomOK)
			{
				Maze[i+1][j] = 'P';
				PushToStack(i+1, j, PathLastQPointer);  
			}
			if (bTopOK)
			{
				Maze[i-1][j] = 'P';
				PushToStack(i-1, j, PathLastQPointer);
			}
		}
		else if (bRightOK)
		{
			newi = i;
			newj = j+1;
			
			if (bLeftOK)
			{
				Maze[i][j-1] = 'P';
				PushToStack(i, j-1, PathLastQPointer);	    
			}
			if (bBottomOK)
			{
				Maze[i+1][j] = 'P';
				PushToStack(i+1, j, PathLastQPointer); 
			}
			if (bTopOK)
			{
				Maze[i-1][j] = 'P';
				PushToStack(i-1, j, PathLastQPointer);	    
			}
		}
		else 
		{
			bool bPopSuccess = PopFromStack(newi, newj, newPathLastQPointer, Maze);
			
			if (!bPopSuccess)
			{
				if (NoOfExits == 0)
				{
					cout << "Sorry There is no way out." << endl;
				}
				break;
			}
		}
		
		if ( (newi != -1) && (newj != -1) ) // We do not have newPathLastQPointer in other cases, we have it only we do Pop
		{
			i = newi;
			j = newj;
			if (newPathLastQPointer != NULL) // Valid only when we do a Pop Operation.
			   PathLastQPointer = newPathLastQPointer;
		}
		else
		{
			cout << "Something went wrong, Impossible State." << endl;
			break;
		}		
    }
    
    cout << endl << endl << "No of Paths to Exit = " << NoOfExits << endl;
    cout << endl << "At End of Program the Input Maze is as follows: " << endl;
    PrintMaze(Maze, iMaxRows, iMaxCols);
    cout << endl << endl <<  "Exit found at " << "Row: " << i << " Col: " << j << endl;
}

void PushToStack(int RowIndex, int ColIndex, PathQueueNode* PathLastQPointer)
{
	StackNode* NewNode = new StackNode;
	
	NewNode->RowIndex = RowIndex;
	NewNode->ColIndex = ColIndex;
	NewNode->SavedPathLastQPointer = PathLastQPointer;
	
	NewNode->next = NULL;
	
	if (TopPointer == NULL)
	   TopPointer = NewNode;
	else
	   NewNode->next = TopPointer;
	   
	TopPointer = NewNode;  	
}


bool PopFromStack(int &newi, int &newj, PathQueueNode* &newPathLastQPointer, char** Maze) 
{
    if (TopPointer == NULL)
	   return false; 
       
    newi = TopPointer->RowIndex;
    newj = TopPointer->ColIndex;
    newPathLastQPointer = TopPointer->SavedPathLastQPointer; 
	    
    // Delete PathQueue Nodes from SavedLastQPointer to NULL. Delete the nodes in the Previous Path that are NOT a part of the Popped Node's Saved Path.
	// The Deleted Path Nodes can be a dead end OR a previous path to success, given we are finding multiple paths to E (from S via Popped Node).
    PathQueueNode* temp = NULL;
    if ( (TopPointer->SavedPathLastQPointer != NULL) && (TopPointer->SavedPathLastQPointer->Next != NULL) )
        temp = TopPointer->SavedPathLastQPointer->Next;  // This is the starting node of the Previous Path we are discarding / deleting.
    while (temp != NULL)
    {
        PathQueueNode* saveTemp = temp;	
        if (Maze[temp->RowIndex][temp->ColIndex] == 'V') // Change the Discarded or Not Required Segment of the nextious Successfull Path to '0'.
		    Maze[temp->RowIndex][temp->ColIndex] = '0';	
        temp = temp->Next;
			
        delete saveTemp;		
    }
	    
    // Deleting the Old Top.
    StackNode* tempTop = TopPointer;
    TopPointer = TopPointer->next;
    delete tempTop; 	 
    
	return true; 
  
}

void EnqueuePath(int i, int j)
{
	PathQueueNode* NewNode = new PathQueueNode;
	NewNode->RowIndex = i;
	NewNode->ColIndex = j;
	NewNode->Next = NULL;
	
	if (PathLastQPointer == NULL)
	   PathLastQPointer = NewNode;
	else
	   PathLastQPointer->Next = NewNode;
	
	PathLastQPointer = NewNode;
	
	if (PathStartQPointer == NULL)
	   PathStartQPointer = NewNode;      
}

void Dequeue(char** Maze, int PathScore[], int PathScoreIndex)
{
	if (PathStartQPointer == NULL)
	  return;
	
	PathScore[PathScoreIndex] = 1; // Includes taking the last step to 'E'. PathScore gives the number of steps taken from 'S' to 'E'.
	
	PathQueueNode* tempPathStartQPointer = PathStartQPointer;
	while (tempPathStartQPointer != NULL)
	{
		PathQueueNode* Temp = tempPathStartQPointer;
		
		//cout << "Row = " << Temp->RowIndex << " Col = " << Temp->ColIndex << endl;
		
		if ( (Maze[Temp->RowIndex][Temp->ColIndex] != 'S') && (Maze[Temp->RowIndex][Temp->ColIndex] != 'E') )
		{
		   Maze[Temp->RowIndex][Temp->ColIndex] = '*';
		   PathScore[PathScoreIndex]++;
	    }
	    
		tempPathStartQPointer = tempPathStartQPointer->Next;
		
		// We do not want to delete the Nodes, as this will be a shared path segment for another route. 
		// Note, the unwanted nodes (the ones that form a dead end or part of a successfull path) are deleted in the POP function. 
		//delete Temp; 
    }  
	
}

void CopyMaze(char** Maze, char** MazeCopy, int iMaxRows, int iMaxCols)
{
	for (int i = 0; i < iMaxRows; i++)
	{
		for (int j = 0; j < iMaxCols; j++)
		{
			MazeCopy[i][j] = Maze[i][j];
		}
	}
}

void DeleteMazeCopy(char** MazeCopy, int iMaxRows)
{
	for (int i = 0; i < iMaxRows; i++)
	{
		if (MazeCopy[i] != NULL)
		  delete[] MazeCopy[i];
	}
	delete[] MazeCopy;
}