NE Paths

I need to create a program that prints the complete path for every possible north-east path recursively.. I have created a method that finds the paths, but the further it goes recursively the less points it returns-- can anyone help return a full path?

Example for prog2.dat:
2 //size of matrix
1 0 //beginning point
0 1 //ending point
[code]
public class prog2
{
public static void main(String args[]) throws Exception
{
Scanner input = new Scanner(new FileReader("prog2.dat"));
int max= input.nextInt();

for(int row=0; rowex)
findPath(sx-1,sy,ex,ey);
if(sy<ey)
findPath(sx,sy+1,ex,ey);

return false;
}


}
[/code]
Thank you for any input!!

Comments

  • Example output is:
    (0,0)(0,1)
    (1,0)(1,1)

    (1,0)(0,0)(0,1)
    (1,1)(0,1) //where it needs to return (1,0)(1,1)(0,1)
  • : Example output is:
    : (0,0)(0,1)
    : (1,0)(1,1)
    :
    : (1,0)(0,0)(0,1)
    : (1,1)(0,1) //where it needs to return (1,0)(1,1)(0,1)
    The (1,0) is left out, because it already has been printed. This become clear if you trace how the program handles the various calls.
    Here's how the program calls each different line. The indentation indicates the level of recursion:
    [code]
    findPath(1, 0, 0, 1)
    print(1, 0)
    if sx > ex: findPath(0, 0, 0, 1)
    print(0, 0)
    if sx > ex:
    if sy < ey: findPath(0, 1, 0, 1)
    print(0, 1)
    if sx == ex & sy == ey: println; return true
    return false
    if sy < ey: findPath(1, 1, 0, 1)
    print(1, 1)
    if sx > ex: findPath(0, 1, 0, 1)
    print(0, 1)
    if sx == ex & sy == ey: println; return true
    if sy < ey:
    return false
    return false
    return false
    [/code]
    As you can see only at the top-level gets the print(sx, sy) called. In between the if (sx > ex) and if (sy < ey) the print(sx, sy) never gets called, which means that the first print is the updated sy.
  • Any advice on achieving the right output? I've been thinking about it for a while, but I can't seem to get anything to work.

    Do I need to scrap this algorithm and try again?

    Thank you very much for your help. :)
  • double post.
  • : Any advice on achieving the right output? I've been thinking about
    : it for a while, but I can't seem to get anything to work.
    :
    : Do I need to scrap this algorithm and try again?
    :
    : Thank you very much for your help. :)
    :
    I would do just that.
    The algorithm you should be using is as follows:
    [code]
    public void findPath(currentPath, endpoint) {
    for(point : adjacent points to currentPath.last()) {
    if (point == endpoint) {
    print(currentPath+point)
    } else {
    findPath(currentpath+point, endpoint)
    }
    }
    }
    [/code]
    The for loops through all the (necessary) adjacent points of last point in the path. This if currentPath is 1 point with location (0, 2), it should loop through (1, 2), (1, 1), and (0, 1) for your implementation. If none of those points are the endpoint, the function is called again with each of those points as the last element in the path. For (1, 2) it will loop through (2, 2), (2, 1), and (1, 1).
    Only when one of the adjacent points is the end point is the entire path printed.
    There are some difficulties to tackle with implementing this algorithm, but this is an algorithm which will to work.
  • Thank you very much for all of your help-- I ended up taking a few steps back and thinking about it as a tree or double linked list and it made me think of a really simple solution:Pass a string along so it can keep track of it's path.

    [code]
    public static void findPath(int sx, int sy, int ex, int ey, String str)
    {
    str+="("+sx+","+sy+")";

    if((sx==ex) && (sy==ey))
    System.out.println(str);

    if(sx>ex)
    findPath(sx-1,sy,ex,ey,str);
    if(sy<ey)
    findPath(sx,sy+1,ex,ey,str);
    }
    [/code]
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories