#include "BFS.h"

void BFS::MazeSearch(char** maze, int rows, int cols, PathGenerator::Location startpoint, int rowExit, int colExit) {

	int** visited = new int* [rows];
	for (int i = 0; i < rows; i++) {
		visited[i] = new int[cols];
		for (int j = 0; j < cols; j++) {
			visited[i][j] = 0; 
		}
	}

	Location** pre = new Location * [rows];
	for (int i = 0; i < rows; i++) {
		pre[i] = new Location[cols];
	}

	std::queue<Location> q;

	q.push(startpoint);

	Location curr; // current location
	// initialize north, west, south and east
	Location north, west, south, east;
	bool found = false;

	while (!(q.empty())) {
		curr = q.front();
		q.pop();
		visited[curr.row][curr.col] = 1;

		north.row = curr.row - 1;
		north.col = curr.col;
		if (north.row >= 0 && north.row < rows &&
			north.col >= 0 && north.col < cols) {
			if ((maze[north.row][north.col] == Maze_Char_Exit) && (maze[north.row][north.col]  == maze[rowExit][colExit])) {
				found = true;
				break;
			}
			else if (maze[north.row][north.col] == Maze_Char_Space &&
				visited[north.row][north.col] != 1) {
				q.push(north);
				visited[north.row][north.col] = 1;
				pre[north.row][north.col] = curr;
			}
		}

		west.row = curr.row;
		west.col = curr.col - 1;
		if (west.row >= 0 && west.row < rows &&
			west.col >= 0 && west.col < cols) {
			if ((maze[west.row][west.col] == Maze_Char_Exit) && (maze[west.row][west.col] == maze[rowExit][colExit])){
				found = true;
				break;
			}
			else if (maze[west.row][west.col] == Maze_Char_Space &&
				visited[west.row][west.col] != 1) {

				q.push(west);
				visited[west.row][west.col] = 1;
				pre[west.row][west.col] = curr;
			}
		}

		south.row = curr.row + 1;
		south.col = curr.col;
		if (south.row >= 0 && south.row < rows && south.col >= 0 &&
			south.col < cols) {
			if ((maze[south.row][south.col] == Maze_Char_Exit) && (maze[south.row][south.col] == maze[rowExit][colExit])){
				found = true;
				break;
			}
			else if (maze[south.row][south.col] == Maze_Char_Space &&
				visited[south.row][south.col] != 1) {
				q.push(south);
				visited[south.row][south.col] = 1;
				pre[south.row][south.col] = curr;
			}
		}

		east.row = curr.row;
		east.col = curr.col + 1;
		if (east.row >= 0 && east.row < rows && east.col >= 0 &&
			east.col < cols) {
			if ((maze[east.row][east.col] == Maze_Char_Exit) && (maze[east.row][east.col] == maze[rowExit][colExit])){
				found = true;
				break;
			}
			else if (maze[east.row][east.col] == Maze_Char_Space &&
				visited[east.row][east.col] != 1) {
				q.push(east);
				visited[east.row][east.col] = 1;
				pre[east.row][east.col] = curr;
			}
		}
	}

	//delete the visited array  
	for (int i = 0; i < rows; i++) {
		delete[] visited[i];
	}
	delete[] visited;

	//no path 
	if (!found) {  
		for (int i = 0; i < rows; i++) {
			delete[] pre[i];
		}
		delete[] pre;
	}

	//path found  
	else {
		while (maze[curr.row][curr.col] != Maze_Char_Start) {
			maze[curr.row][curr.col] = Maze_Char_Path;		
			curr = pre[curr.row][curr.col];
		}

		for (int i = 0; i < rows; i++) {
			delete[] pre[i];
		}
		delete[] pre;
	}
}