CODEWITHSUNDEEP
javaalgorithmrecursion
user3100137
user3100137

Reputation:

longest path in a maze

i have an assignement to find the longest path in a maze using recursion. i also have to show the process of searching for the path. I think i get the idea of how its supposed to be done but i get myself into truble when it comes to the code. Now i don't want the code done for me. I just need some pointers and some tips on my logic. . this is my recursive method so far. I guess there is no point sharing the graphics methods since the recursive method is where im stuck at.

void findPath(Point a){ // starting point

    if (a  == mazeEnd){ 
        pathAdd(a); 
        return;
    } 
    if (wall(a)) return; 
    if (visited(a)) return; 
    if (a == mazeStart) pathAdd(a);

    length++ 
    printPath;

    findPath(new Point(a.x+1, a.y));
    findPath(new Point(a.x, a.y+1)); 
    findPath(new Point(a.x-1, a.y)); 
    findPath(new Point(a.x, a.y-1)); 

}

UPDATE: ok thank you all for the tips and let me further explain. the entire board is a grid. i read the walls, starting and enting point from a file. i create a list for the walls and palce them on the board. wall(a) checks if a coordinate is the walls array. pathAdd is a method taht adds a coordinate to the path array. but doesnt that means that after it has complyted all the paths, the path array will have every coordinate in that board except the ones that are walls? At least in the wway i have coded it. Thats my major issue i think. If i can get the list to only hold one path i guess ill figure out how to get the largest out of it.

Upvotes: 0

Views: 3102

Answers (4)

Anthony Kiskaden
Anthony Kiskaden

Reputation: 311

findPath(a) should return a length. Specifically it should return the max(findPath(up) || findpath(down) || findPath(left) || findPath(right)) + 1. If wall(a) or visisted(a), you can return a large negative number and for mazeEnd(a) return 1. To print the path you need to add the new Point that returns the greatest length with pathAdd(). Hope that helps :)

Upvotes: 0

Sabuj Hassan
Sabuj Hassan

Reputation: 39443

You are restricting to move further when a cell/point is visited. But I didn't see you marked a cell/point as visited in your code. You can do this just before moving into the four directions. If you do not do this, your recursion will never get an end.

Upvotes: 0

corsiKa
corsiKa

Reputation: 82589

There's a few omissions I see.

  1. You never add the current point to your path - you only ever add the start or the end.
  2. You never mark any points as visited.
  3. You check to see if things are visited, but you don't have a way of knowing if they were visited in this path or some other path. Consider the scenario where there is some islands of walls, and you could reach a point via two or more routes: one of those routes may be longer than the other routes, but you're more likely to reach it via the short route first. It will end up being ignored, when it should be considered as a candidate for both routes.
  4. You are triggering length++ on every call to find path. If you do your first node, and then the 4 nodes around it, you're going to have a length of 5 when your longest is 2. That's no good!

Upvotes: 1

M21B8
M21B8

Reputation: 1887

If you passed a list into the method, when you found a path that made it to the end of the maze, you could add it to the list. then when recursion finishes, you can iterate through the list to find the longest path.

Upvotes: 0

Related Questions