Accounting for walking in a Circle

#include <iostream>
#include <cassert>
#include <queue>
#include <stack>
#include <string>

using namespace std;

class Coord
{
public:
	Coord(int r, int c) : m_row(r), m_col(c) {}
	int r() const { return m_row; }
	int c() const { return m_col; }
private:
	int m_row;
	int m_col;
};

// Returns true if a path exists from (starting_row, starting_col) to (ending_row, ending_col)
bool pathExists(string maze[], int number_of_rows, int number_of_cols, int starting_row, int starting_col, int ending_row, int ending_col)
{
	// Initialize a Queue of Coordinates
	queue<Coord> queue_of_coordinates;

	// Push the Queue by putting in the starting row and starting col
	// Assignment instructions that starting point is always going to be a "." and not a wall
	queue_of_coordinates.push(Coord(starting_row, starting_col));

	// The maze is an array of strings
	// While we have only defined the rows of the string, the "columns" of the string are implict because they are each of the individual characters of the string
	// We will overwrite that as D to mark it as discovered
	maze[starting_row][starting_col] = 'D';

	while (!queue_of_coordinates.empty())
	{
		// Pop the queue by taking the coordinate in queue and popping it
		// Different from stack because stack pops the most recent item whereas queue pops the item that has been there the longest
		Coord current = queue_of_coordinates.front();
		queue_of_coordinates.pop();

		int current_row = current.r();
		int current_col = current.c();

		if (current_row == ending_row && current_col == ending_col)
			return true;

		// Remember to use IF statements for the following, not else if statements
		// You need to put each and every possible point on the stack

		// First, check EAST, which is (r, c+1)
		if (maze[current_row][current_col + 1] == '.')
		{
			queue_of_coordinates.push(Coord(current_row, current_col + 1));
			maze[current_row][current_col + 1] = 'D';
		}

		// Second, check NORTH, which is (r-1, c)
		if (maze[current_row - 1][current_col] == '.')
		{
			queue_of_coordinates.push(Coord(current_row - 1, current_col));
			maze[current_row - 1][current_col] = 'D';
		}

		// Third, check WEST, which is (r, c-1)
		if (maze[current_row][current_col - 1] == '.')
		{
			queue_of_coordinates.push(Coord(current_row, current_col - 1));
			maze[current_row][current_col - 1] = 'D';
		}

		// Finally, check SOUTH, which is (r+1, c)
		if (maze[current_row + 1][current_col] == '.')
		{
			queue_of_coordinates.push(Coord(current_row + 1, current_col));
			maze[current_row + 1][current_col] = 'D';
		}
	}

	return false;
}

void printMaze(string maze[], int number_of_rows, int number_of_cols)
{
	for (int i = 0; i < number_of_rows; i++)
	{
		for (int j = 0; j < number_of_cols; j++)
		{
			cout << maze[i][j];
		}
		cout << endl;
	}

	cout << endl;
}

bool isDeadEnd(string maze[], int starting_row, int starting_col, int ending_row, int ending_col, int current_row, int current_col)
{
	// If there are 3 directions unavailable, then it is a dead end
	// There will always be one direction available (the one that lead to that point).
	//
	// 3 different characters mark if a direction is unavailable: walls, N, or .
	// . represents a path never taken when proving if the path exists or not
	// x represents a wall that we obviously we cannot walk into
	// N represents a point we've marked that leads nowhere

	if (current_row == starting_row && current_col == starting_col)
		return false;

	if (current_row == ending_row && current_col == ending_col)
		return false;

	int number_of_directions_unavailable = 0;

	// First, check EAST, which is (r, c+1)
	if (maze[current_row][current_col + 1] == '.' || maze[current_row][current_col + 1] == 'X' || maze[current_row][current_col + 1] == 'N')
		number_of_directions_unavailable++;

	// Second, check NORTH, which is (r-1, c)
	if (maze[current_row - 1][current_col] == '.' || maze[current_row - 1][current_col] == 'X' || maze[current_row - 1][current_col] == 'N')
		number_of_directions_unavailable++;

	// Third, check WEST, which is (r, c-1)
	if (maze[current_row][current_col - 1] == '.' || maze[current_row][current_col - 1] == 'X' || maze[current_row][current_col - 1] == 'N')
		number_of_directions_unavailable++;

	// Last, check SOUTH, which is (r+1, c)
	if (maze[current_row + 1][current_col] == '.' || maze[current_row + 1][current_col] == 'X' || maze[current_row + 1][current_col] == 'N')
		number_of_directions_unavailable++;



	if (number_of_directions_unavailable > 2)
	{
		maze[current_row][current_col] = 'N';
		return true;
	}

	return false;
}

void isDeadEndAfterRetrace(string maze[], int starting_row, int starting_col, int ending_row, int ending_col, int current_row, int current_col)
{
	if (current_row == starting_row && current_col == starting_col)
		return;

	if (current_row == ending_row && current_col == ending_col)
		return;

	int number_of_directions_unavailable = 0;

	// First, check EAST, which is (r, c+1)
	if (maze[current_row][current_col + 1] == '.' || maze[current_row][current_col + 1] == 'X' || maze[current_row][current_col + 1] == 'N' || maze[current_row][current_col + 1] == 'D')
		number_of_directions_unavailable++;

	// Second, check NORTH, which is (r-1, c)
	if (maze[current_row - 1][current_col] == '.' || maze[current_row - 1][current_col] == 'X' || maze[current_row - 1][current_col] == 'N' || maze[current_row - 1][current_col] == 'D')
		number_of_directions_unavailable++;

	// Third, check WEST, which is (r, c-1)
	if (maze[current_row][current_col - 1] == '.' || maze[current_row][current_col - 1] == 'X' || maze[current_row][current_col - 1] == 'N' || maze[current_row][current_col - 1] == 'D')
		number_of_directions_unavailable++;

	// Last, check SOUTH, which is (r+1, c)
	if (maze[current_row + 1][current_col] == '.' || maze[current_row + 1][current_col] == 'X' || maze[current_row + 1][current_col] == 'N' || maze[current_row + 1][current_col] == 'D')
		number_of_directions_unavailable++;

	if (number_of_directions_unavailable > 2)
	{
		maze[current_row][current_col] = 'N';
		return;
	}

	return;
}

bool findDirections(string maze[], int number_of_rows, int number_of_cols, int starting_row, int starting_col, int ending_row, int ending_col)
{
	/*
	* Psuedo Code Approach:
	* First run to check if the path even exists
	* Checking if the path exists marks each discoverable area as a D
	*
	* For this approach because we are checking individual paths, we will use a stack
	*
	* We'll mark each point we retrace as R
	* Go through each D until you reach either the beginning or nowhere
	* If you reach the beginning, then that is the path and we will write directions
	* We will check the surroundings to see if it ends up in nowhere
	* We will then pop the stack to go back to the previous point
	*
	* One problem that arises is that if you find a path, there are still some coordinates that were pushed onto the stack that didn't lead anywhere
	* After we've found a path, we will write a helper program that checks every non starting and ending point to ensure that they are connected in front and behind
	* That is to say that each non starting and ending point R is connected to two other Rs
	*/

	/*
	Psuedo Code Approach #2:
	* First run to check if the path even exists
	* Checking if the path exists marks each discoverable area as a D
	*
	*
	*/

	/*

	bool check_pathExists = pathExists(maze, number_of_rows, number_of_cols, starting_row, starting_col, ending_row, ending_col);

	if (check_pathExists == false)
	{
		cout << "There are no directions because there is no path that exists." << endl;
		return false;
	}

	*/

	// If a path exists, but it's because you do nothing, simply say do nothing
	if (starting_row == ending_row && starting_col == ending_col)
	{
		cout << "There are no directions because the start point is the same as the end point." << endl;
		return true;
	}

	stack<Coord> stack_of_retraced_coords;
	stack_of_retraced_coords.push(Coord(ending_row, ending_col));

	// Instead of popping coordinates, we will actually keep them in the stack
	// We will pop coordinates when we reach a dead end or reach the end
	while (!stack_of_retraced_coords.empty())
	{
		// Get the coordinates of whatever is currently on top of the stack
		// Then make decisions based on those coordinates
		Coord current = stack_of_retraced_coords.top();

		int current_row = current.r();
		int current_col = current.c();

		if (current_row == starting_row && current_col == starting_col)
		{
			break;
		}
		// Remember to use IF statements for the following, not else if statements
		// You need to put each and every possible point on the stack

		// Now that we've put all the possibilities on the stack, let's check if the current is at a dead end or not
		// If it is at a dead end, we will mark that point as N and then pop it from the stack
		// Popping the current stack will mean we will go to the previous point and then check if is also a dead end after we updated this current point to N

		while (isDeadEnd(maze, starting_row, starting_col, ending_row, ending_col, current_row, current_col))
		{
			stack_of_retraced_coords.pop();

			current = stack_of_retraced_coords.top();
			current_row = current.r();
			current_col = current.c();
		}

		int has_moved = 0;

		// First, check EAST, which is (r, c+1)
		if (maze[current_row][current_col + 1] == 'D')
		{
			stack_of_retraced_coords.push(Coord(current_row, current_col + 1));
			maze[current_row][current_col + 1] = 'R';
			has_moved++;
		}

		// Second, check NORTH, which is (r-1, c)
		if (maze[current_row - 1][current_col] == 'D')
		{
			stack_of_retraced_coords.push(Coord(current_row - 1, current_col));
			maze[current_row - 1][current_col] = 'R';
			has_moved++;
		}

		// Third, check WEST, which is (r, c-1)
		if (maze[current_row][current_col - 1] == 'D')
		{
			stack_of_retraced_coords.push(Coord(current_row, current_col - 1));
			maze[current_row][current_col - 1] = 'R';
			has_moved++;
		}

		// Last, check SOUTH, which is (r+1, c)
		if (maze[current_row + 1][current_col] == 'D')
		{
			stack_of_retraced_coords.push(Coord(current_row + 1, current_col));
			maze[current_row + 1][current_col] = 'R';
			has_moved++;
		}

		if (has_moved == 0)
		{
			isDeadEnd(maze, starting_row, starting_col, ending_row, ending_col, current_row, current_col);
			stack_of_retraced_coords.pop();
		}
	}

	stack_of_retraced_coords.pop();

	while (!stack_of_retraced_coords.empty())
	{
		Coord current = stack_of_retraced_coords.top();
		int current_row = current.r();
		int current_col = current.c();
		isDeadEndAfterRetrace(maze, starting_row, starting_col, ending_row, ending_col, current_row, current_col);
		stack_of_retraced_coords.pop();
	}

	return true;
}

int main()
{
	string maze1[10] = {
		  "XXXXXXXXXX",
		  "X.X..X...X",
		  "X.XX.X.XXX",
		  "X....X.X.X",
		  "XX.X.X...X",
		  "XXX..X.X.X",
		  "X...X...XX",
		  "X.XX..X.XX",
		  "X....X...X",
		  "XXXXXXXXXX",
	};

	string maze2[10] = {
	  "XXXXXXXXXX",
	  "X.X..X...X",
	  "XXXX.X.XXX",
	  "X....X.X.X",
	  "XX.X.X...X",
	  "XXX..X.X.X",
	  "X...X...XX",
	  "X.XX..X.XX",
	  "X....X...X",
	  "XXXXXXXXXX",
	};

	string maze3[10] = {
	  "XXXXXXXXXX",
	  "XX.....XXX",
	  "X..XX....X",
	  "X...X...XX",
	  "X.X.XXX..X",
	  "XXXX..X..X",
	  "XX....X..X",
	  "X.......XX",
	  "X..XXXXXXX",
	  "XXXXXXXXXX",
	};

	string maze4[10] = {
	  "XXXXXXXXXX",
	  "XX.....XXX",
	  "X..XX....X",
	  "X...X...XX",
	  "X.X.XXX..X",
	  "XXXX..X..X",
	  "XX....X..X",
	  "X.X.....XX",
	  "X..XXXXXXX",
	  "XXXXXXXXXX",
	};

	string maze5[6] = {
	  "XXXXXX",
	  "XX.XXX",
	  "XX.XXX",
	  "X...XX",
	  "XX.XXX",
	  "XXXXXX",
	};

	string maze6[10] = {
		"XXXXXXXXXX",
		"X.XXXXXXXX",
		"X...XXXX.X",
		"X.XXXXXX.X",
		"X.XXXXXX.X",
		"X.XXXXXX.X",
		"X.XXXXXX.X",
		"X.XXXXXX.X",
		"X........X",
		"XXXXXXXXXX",
	};

	cout << "Maze 5" << endl;
	pathExists(maze5, 6, 6, 4, 2, 1, 2);
	printMaze(maze5, 6, 6);
	findDirections(maze5, 6, 6, 4, 2, 1, 2);
	printMaze(maze5, 6, 6);

	cout << "Maze 1" << endl;
	pathExists(maze1, 10, 10, 8, 6, 1, 1);
	printMaze(maze1, 10, 10);
	findDirections(maze1, 10, 10, 8, 6, 1, 1);
	printMaze(maze1, 10, 10);

	cout << "Maze 6" << endl;
	pathExists(maze6, 10, 10, 8, 8, 1, 1);
	printMaze(maze6, 10, 10);
	findDirections(maze6, 10, 10, 8, 8, 1, 1);
	printMaze(maze6, 10, 10);

	cout << "Maze 3" << endl;
	pathExists(maze3, 10, 10, 4, 3, 7, 1);
	printMaze(maze3, 10, 10);
	findDirections(maze3, 10, 10, 4, 3, 7, 1);
	printMaze(maze3, 10, 10);

}