Rat in a Maze

rat_in_maze.cpp

#include <iostream>
#include <vector>
#include <algorithm>

#pragma once
#define MATRIX_SIZE 5

struct location {
	int row ;
	int col ;
	double distance;
};

std::vector<std::vector<location>> min_moves_paths;

void print_matrix(int maze_matrix[MATRIX_SIZE][MATRIX_SIZE])
{
	std::cout << '\n';
	for (int i = 0; i < MATRIX_SIZE; i++)
	{
		for (int j = 0; j < MATRIX_SIZE; j++)
		{
			std::cout << maze_matrix[i][j] << '\t';
		}
		std::cout << '\n';
	}
	std::cout << '\n';
}

void store_location(std::vector<location>& possible_locations, int row, int col, location dst_loc, int maze_matrix[MATRIX_SIZE][MATRIX_SIZE])
{
	// store the location as a possible location iff it is 0, i.e empty
	if (maze_matrix[row][col] == 0)
	{
		location nxt_loc;
		nxt_loc.row = row;
		nxt_loc.col = col;
		nxt_loc.distance = std::sqrt(std::pow((dst_loc.row - nxt_loc.row), 2) + std::pow((dst_loc.col - nxt_loc.col), 2));
		possible_locations.push_back(nxt_loc);
	}
}

std::vector <location> get_next_loc(location cur_loc, location dst_loc, int maze_matrix[MATRIX_SIZE][MATRIX_SIZE])
{
	/*
	 from the cur_loc, we can move in 4 possible directions, UP, DOWN, LEFT, RIGHT
	 UP    = (row - 1, col)
	 DOWN  = (row + 1, col)
	 LEFT  = (col - 1, row)
	 RIGHT = (col + 1, row)
	*/

	std::vector<location> possible_locations;

	int row = cur_loc.row;
	int col = cur_loc.col;

	// check for RIGHT location 
	if (row + 1 < MATRIX_SIZE)
	{
		store_location(possible_locations, row + 1, col, dst_loc, maze_matrix);
	}
	// check for DOWN location 
	if (col + 1 < MATRIX_SIZE)
	{
		store_location(possible_locations, row , col + 1, dst_loc, maze_matrix);
	}
	// check for UP location
	if (col - 1 >= 0)
	{
		store_location(possible_locations, row, col - 1, dst_loc, maze_matrix);
	}
	// check for LEFT location
	if (row - 1 >= 0)
	{
		store_location(possible_locations, row - 1, col, dst_loc, maze_matrix);
	}
	
	return possible_locations;
}

void sort_locations(std::vector<location>& possible_locations)
{
	// sort the possible locations in increasing order of the distance from the destination location
	if (possible_locations.size() > 1)
	{
		// create and store the possible locations in a temp_locations vector
		std::vector<location> temp_locations = possible_locations;

		// clear the possible_locations vector as we would be storing the elements in increasing order in it
		possible_locations.clear();

		if (temp_locations.size())
		{
			// check for min_dist location, remove it from the temp_locations vector and then check again till no location left inside temp_locations vector
			while (temp_locations.size())
			{
				double min_dist(MATRIX_SIZE*MATRIX_SIZE);
				int min_dist_index;
				for (int i = 0; i<temp_locations.size();i++)
				{
					location loc = temp_locations[i];
					double distance = loc.distance;
					if (distance <= min_dist)
					{
						min_dist = distance;
						min_dist_index = i;
					}
				}

				// get the min move index element
				location min_dist_location = temp_locations[min_dist_index];

				// store the min_dist location in possible_locations vector
				possible_locations.push_back(min_dist_location);

				// remove the element from the temp_locations vector
				temp_locations.erase(temp_locations.begin() + min_dist_index);
			}
		}
	}
}

void reach_dst(location cur_loc, location dst_loc, int maze_matrix[MATRIX_SIZE][MATRIX_SIZE])
{
	// create a static vector path_traced which will store the all the locations from starting to DEAD END or dst_loc
	static std::vector<location> path_traced;
	
	// if dst_loc is -1, i.e it is a block then return as we cannot reach there
	if (maze_matrix[dst_loc.row][dst_loc.col] == -1)
	{
		std::cout << "No Solution Exists!!" << std::endl;
		return;
	}

	// store the cur_loc in the path_traced vector
	path_traced.push_back(cur_loc);
	
	// check whether we have reached the dst_loc
	if (cur_loc.row == dst_loc.row && cur_loc.col == dst_loc.col)
	{
		if (min_moves_paths.size())
		{
			// if the size of the last vector inside the min_moves_paths vector is larger than the current path_traced size then remove that last vector
			if (min_moves_paths[min_moves_paths.size() - 1].size() >= path_traced.size())
			{
				min_moves_paths.pop_back();
			}
		}
		//store the current path_traced vector in min_moves_paths vector
		min_moves_paths.push_back(path_traced);
		return;
	}

	if (min_moves_paths.size())
	{
		// if the size of the last vector inside the min_moves_paths vector is smaller than the current path_traced vector, then return as it is greater than the previous path_traced
		if (min_moves_paths[min_moves_paths.size() - 1].size() < path_traced.size())
		{
			return;
		}
	}

	// mark the cur_loc as 1 so that it is eliminated as a possible location when next location is searching for possible locations
	maze_matrix[cur_loc.row][cur_loc.col] = 1;

	// get the next possible locations
	std::vector<location> possible_locations = get_next_loc(cur_loc,dst_loc, maze_matrix);
	if (!possible_locations.size())
	{
		// if No possible locations found, i.e we hit DEAD END, mark that location as -1 and return to previous location
		maze_matrix[cur_loc.row][cur_loc.col] = -1;
		return;
	}
	else
	{
		// sort the possible locations in increasing order of the distance from the dst_loc, as we want to find the minimum moves path first
		sort_locations(possible_locations);

		// loop through all the possible locations to reach the dst_loc
		for (location nxt_loc : possible_locations)
		{
			// recurse with the next possible location to reach the dst_loc
			reach_dst(nxt_loc, dst_loc, maze_matrix);	
			
			// after reaching DEAD END or dst_loc, mark that location as 0 as some other path might want to access that location
			maze_matrix[nxt_loc.row][nxt_loc.col] = 0;

			// remove the cur_loc from the path_traced as it has been used 
			path_traced.pop_back();
		}
	}
}

void rat_in_maze_function()
{
	//create a NxN matrix and fill it with 0s
	int maze_matrix[MATRIX_SIZE][MATRIX_SIZE]={ {  0,  0,  0,  0 } ,
                                              { -1, -1, -1,  0 } ,
                                              {  0,  0, -1,  0 } ,
                                              {  0, -1, -1,  0 } ,
                                              {  0, -1,  0, -1 } };

	print_matrix(maze_matrix);

	//start from cur_loc and reach dst_loc
	location cur_loc = { 0, 0 };
	location dst_loc = { 2, 1 };
	reach_dst(cur_loc, dst_loc, maze_matrix);
	print_matrix(maze_matrix);

	std::cout << "Number of Solutions with minimum moves: " << min_moves_paths.size() << std::endl << std::endl;;

	if (min_moves_paths.size())
	{
		for (auto temp : min_moves_paths)
		{
			int moves(0);
			for (auto loc : temp)
			{
				moves++;
				std::cout << "(" << loc.row << "," << loc.col << ") \n";
			}
			std::cout << "Moves taken: " << moves -1<< std::endl;
		}
	}
	else
	{
		std::cout << "No Solution Exists!!" << std::endl;
	}
}


int main()
{
	rat_in_maze_function();
}