breadth first search

[red999]

I implemented a BFS on a maze that I made, but the one problem that I have is that I do not know how to obtain the indices of the path that it took to solve the maze. Right now all my BFS algorithm does it prints out if it is solvable (it reached the exit of the maze)

I currently have a vector called used that holds all the Cells that the BFS algorithm has visited as well as a queue that does what a BFS do. Is there something that I am missing about this BFS algorithm?
Please help. Thanks

Here is my function. Please note that I am assuming that it is right since it reached the end of the maze.

void CMaze::SolveMaze()
{
	queue <Cell*> nextQueue;
	vector <int> used;
	bool found = false;

	nextQueue.push(&s[0]);
	used.push_back(0);

	while(!found)
	{
		Cell *c;
		if((int) nextQueue.size() > 0)
		{
			c = nextQueue.front();
			nextQueue.pop();
		}
		else
			break;
		if(c->pos == size - 1)
		{
			found = true;
			break;
		}
		else
		{
			for(int i = 0; i < c->neighbor.size(); ++i)
			{
				if(!hasN(used, c->neighbor[i]))
				{
					used.push_back(c->neighbor[i]);
					nextQueue.push(&s[c->neighbor[i]]);
				}
			}
		}

	}
	if(found)
		cout << "found" << endl;
} //SolveMaze()

[WaltP]

Keep track of each move. When you generate the next location, add a 'pointer' back to the previous location.

[red999]

I don't really get how that would help me. I believe that I will need to modify my Cell class for that to help. Maybe add linked list?

I know that the BFS grows like a tree and it goes through the k-th level of the tree before the k+1 level. So what I have done is that I have a distance variable for each Cells.

For a 5x5 maze, the distance between the exit and the entrance is 10. When I do this, I can start from the exit and go all the way up to a Cell with distance of 0 which will be the entrance. This way seems to work okay, but it doesn't seem to be as elegant as I have hoped it to be. Once the BFS algorithm finishes, I will need to go back into the maze and check if the Cell with the distance of 9 is the Cell that will lead to the entrance. I still have walls and such. I'll show an illustration

8 _9_ <--- wall under top nine (not valid Cell)
9 10

Is there some other way that I don't need to go back into the maze for a second run?

[WaltP]

Yes.

Keep track of each move. When you generate the next location, add a 'pointer' back to the previous location.

If you know where you came from at each 'node', you can backtrack straight to the beginning. You have your solution.