0

I have a problem that I am working on, and it is to find the shortest path on a grid, when you are given a start point, an end point, and a list of obstacles. I managed to set up a grid by using a vector of vectors, but I'm having trouble in my actual recursive call. For one reason or another, my grid doesn't update when I try to pass it to this function.

The code for my recursive function is as follows

//grid is the grid of walls and openings, currSt is the current Y coordinate
//currAv is the current X coordinate, pathLength is the current length of the path
void findShortestPath(vector<vector<int> >& grid, int currSt,int currAv,int pathLength,int const gridSize)
{
	int solutionLength;
	//checks for solution
	if(isSolution(grid,currSt,currAv))
	{
		printPath(grid,gridSize);
	}
	else if(isValidMove(grid,currSt,currAv-1,gridSize,pathLength,solutionLength))
	{
		grid[currSt][currAv-1]=pathLength;
		pathLength++;
		findShortestPath(grid,currSt,currAv-1,pathLength,gridSize);
	} 
	else if(isValidMove(grid,currSt,currAv+1,gridSize,pathLength,solutionLength))
	{
		grid[currSt][currAv+1]=pathLength;
		pathLength++;
		findShortestPath(grid,currSt,currAv+1,pathLength,gridSize);
	}
	else if(isValidMove(grid,currSt+1,currAv,gridSize,pathLength,solutionLength))
	{
		grid[currSt+1][currAv]=pathLength;
		pathLength++;
		findShortestPath(grid,currSt+1,currAv,pathLength,gridSize);
	} 
	else if(isValidMove(grid,currSt-1,currAv,gridSize,pathLength,solutionLength))
	{
		grid[currSt-1][currAv]=pathLength;
		pathLength++;
		findShortestPath(grid,currSt-1,currAv,pathLength,gridSize);
	}

}
2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by alwaysLearning0
0

Hi,

what do you mean by it doesnt update.
It has to, as you are passing by reference.

And also you are doing a logical mistake,
you are using if, else if.
you can not do if else if here, all of the check has to be individual if.

DSF is done for all possible combinations. if you only do, if and else if, for a given city/node, only the first successful condition block will be executed.
But for DFS, for any given city, all the successful condition (valid paths) need to be traversed.

In plain words, remove the else. check all the condition in "if"

and also:

int solutionLength; what is this for? you are not setting it but passing as recursion method.

You are also setting the visited, but not setting the unvisited. (two hours ago i looked at code of someone else, and he has also similar kind of mistakes. actually exact same??!!)

Edited by alwaysLearning0: more logical mistakes.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.