I have sevral questions about maze - solver algorithms:C
- What is the time complexity of recursive (backtracking) maze-solver?(As an amount of paths in the matrix? - I can`t figure this number..)
- What is the time complexity of BFS based maze-solver?(O(n^2)?) n is a dimension of the squared maze matrix?
- What is the best algoritm to count the number of all possible paths from the source to the destination in the maze?
- Can you propose the idea if and how an it be implemented using parallel computing (opecl/cuda)
Here is the class for my maze solver ,which has brute (recursive) and bfs based version.I implemented it and the questions are based on this maze-solver implementation
//MazeSolver.h
//#define N 5
typedef enum {BLACK,WHITE,GRAY,VISITED} color;
class MazeSolver
{
public:
MazeSolver(){}
struct Cell
{
unsigned int _x;
unsigned int _y;
Cell* _p;
Cell(unsigned int x = 0,unsigned int y = 0, Cell* p = NULL) : _x(x),_y(y),_p(p) {}
bool operator == (const Cell& c)
{
return _x == c._x && _y == c._y;
}
};
bool solveMazeBrute(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<Cell>& path);
bool solveMazeBFS(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<Cell>& path);
private:
std::queue<Cell* > _bfs;
std::vector<Cell* > _cells;
Cell* addCellBFS(color maze[][N],unsigned int n,int x,int y,Cell* p = NULL);
};
//MazeSolver.cpp
MazeSolver::Cell* MazeSolver::addCellBFS(color maze[][N],unsigned int n,int x,int y,Cell* p)
{
if (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == WHITE)
{
Cell* c = new Cell(x,y,p);
maze [x][y] = VISITED;
_bfs.push(c);
_cells.push_back(c);
return c;
}
return NULL;
}
bool MazeSolver::solveMazeBrute(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<MazeSolver::Cell>& path)
{
bool solved = false;
if (xS < 0 || xS >= n || yS < 0 || yS >= n || maze[xS][yS] == VISITED || maze[xS][yS] == BLACK)
{
return false;
}
Cell s(xS,yS);
Cell d(xD,yD);
if (s == d)
{
path.push_front(s);
return true;
}
maze[xS][yS] = VISITED;
if (solveMazeBrute(maze,n,xS + 1,yS,xD,yD,path) ||
solveMazeBrute(maze,n,xS - 1,yS,xD,yD,path) ||
solveMazeBrute(maze,n,xS,yS + 1,xD,yD,path) ||
solveMazeBrute(maze,n,xS,yS - 1,xD,yD,path))
{
path.push_front(s);
solved = true;
}
maze[xS][yS] = WHITE;
return solved;
}
bool MazeSolver::solveMazeBFS(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<Cell>& path)
{
Cell d(xD,yD);
addCellBFS(maze,n,xS,yS);
while(!_bfs.empty())
{
Cell* cur = _bfs.front();
if (*cur == d)
{
while (cur != NULL)
{
path.push_front(*cur);
cur = cur->_p;
}
return true;
}
_bfs.pop();
addCellBFS(maze,n,cur->_x - 1,cur->_y,cur);
addCellBFS(maze,n,cur->_x + 1,cur->_y,cur);
addCellBFS(maze,n,cur->_x,cur->_y - 1,cur);
addCellBFS(maze,n,cur->_x,cur->_y + 1,cur);
}
for(std::vector<Cell*>::iterator itC= _cells.begin();itC != _cells.end();++itC)
{
maze[(*itC)->_x][(*itC)->_y] = WHITE;
delete *itC;
}
return false;
}