Results 1 to 5 of 5
  1. #1
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    88
    Rep Power
    0

    Default Weird problem with backtracking

    Hello, trying to find all paths in matrix, the problem is with the left turn but as for now, after working with a debugger I found that the right call doesn't registered pass the positions i2 j1
    so when it was i2 j0 it went right in position with the marked call in the picture but on the second time it needed to proceed right it fails to do so, but it is odd since it seems like the call is registered, just seems like j is not increased to 2 for some reason.. This is not an assignment BTW.. Thank you.

    Can't attach a picture of it unfortunately...

    Java Code:
    public static void main (String args[]){
            
            
            int [][] matrix = {{8,4,2},
                               {6,3,8},
                               {1,4,9},
                               };
            allPaths(matrix);
        }
    Java Code:
    public static void allPaths(int [][] m){
            int c [][] = new int [m.length][m[0].length];
            allPaths(m,0,0,0);
            
        }
        
        public static void allPaths(int [][] m,int i,int j,int sum){
            if(i == m.length-1 && j == m[0].length-1) {System.out.println(sum);return;}
            if(isValid(m,i,j)){
                if(m[i][j]!=-1)
                sum+=m[i][j];            
                //m[i][j]=-1;
                allPaths(m,i+1,j,sum);//down
                if(m[i][j] != -1 || j==0 || i==m.length-1){
                    m[i][j]=-1;
                    allPaths(m,i,j+1,sum);//right
                }
                if(m[i][j] == -1 || j>0 || i>m.length-1)
                allPaths(m,i,j-1,sum);//left
                }
            }   
        
        public static boolean isValid(int [][] m,int i,int j){
            if(i < m.length && i > -1 && j < m[0].length && j > -1 && m[i][j]!=-1) return true; return false;
        }

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    19,964
    Rep Power
    31

    Default Re: Weird problem with backtracking

    Do you have a java programming question?

    Note: The compact formatting of the code makes it hard to read and understand.
    Please fix the formatting to make the code more readable:
    Add {}s for all conditional code blocks
    only one statement on a line
    Last edited by Norm; 03-23-2017 at 01:58 PM.
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Weird problem with backtracking

    First, could you explain what you mean by path (some paths could be closed as a path is a super set of a circuit)?
    And please provide some examples and what you expect the output to be.

    Second, a couple observations.
    1. What is the purpose of the array in line 2 of allpaths()?
    2. Your isValid() method (as was stated already) does not use braces.

    never do this;
    Java Code:
    if () a;
       b
    // do this - even for one liners
       if () {
          a;}
       } else {
          b;
       }
    But for booleans you are essentially doing

    Java Code:
    if (true) {
       return true;
    }
    return false;
    
    //So just do the following:
    
    return i < m.length && i > -1 && j < m[0].length && j > -1
                && m[i][j] != -1;
    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  4. #4
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    88
    Rep Power
    0

    Default Re: Weird problem with backtracking

    Quote Originally Posted by jim829 View Post
    First, could you explain what you mean by path (some paths could be closed as a path is a super set of a circuit)?
    And please provide some examples and what you expect the output to be.

    Second, a couple observations.
    1. What is the purpose of the array in line 2 of allpaths()?
    2. Your isValid() method (as was stated already) does not use braces.

    never do this;
    Java Code:
    if () a;
       b
    // do this - even for one liners
       if () {
          a;}
       } else {
          b;
       }
    But for booleans you are essentially doing

    Java Code:
    if (true) {
       return true;
    }
    return false;
    
    //So just do the following:
    
    return i < m.length && i > -1 && j < m[0].length && j > -1
                && m[i][j] != -1;
    Regards,
    Jim
    Weird problem with backtracking-untitled-1.png

    More about the method itself, it is meant for counting the sum of all the numbers that are in each path.
    A path is one that ends at i==length-1 && j==length-1 (the bottom right corner) could be many paths on the way to it, but should print each one on the screen.

    if this is the matrix:

    {{8,4,2},
    {6,3,8},
    {1,4,9}}

    then 8+6+1+4+9 is a path
    8,4,3,6,1,4,9 is a path and so on

    I solved it already when it is only down and right moves but the left move messes it up although the problem now relies on this particular situation that is showing in the attached picture.
    it doesn't increase the j++ on the second time, it should go right again and it seems like it goes to perform that row in the debugger but you can actually see the the value of j doesn't increase..
    Should be i=2 j=2 but j stays 1 after commi

  5. #5
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    88
    Rep Power
    0

    Default Re: Weird problem with backtracking

    Regardless if anyone knows if I'm on the right way or came across this kind of things before i'd be happy to hear about it.

Similar Threads

  1. I have this weird problem..
    By saber210 in forum New To Java
    Replies: 11
    Last Post: 08-14-2011, 04:29 AM
  2. Weird problem with 36 and 39?
    By jh7468 in forum New To Java
    Replies: 3
    Last Post: 02-06-2011, 08:01 PM
  3. Weird problem with distributing .jar
    By Cynot in forum NetBeans
    Replies: 3
    Last Post: 06-07-2010, 10:01 PM
  4. Weird problem with distributing .jar
    By Cynot in forum New To Java
    Replies: 4
    Last Post: 06-07-2010, 12:03 PM
  5. weird problem
    By GPB in forum New To Java
    Replies: 2
    Last Post: 02-28-2010, 12:04 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •