Results 1 to 4 of 4
  1. #1
    Risvosk is offline Member
    Join Date
    Dec 2011
    Posts
    2
    Rep Power
    0

    Default Java Recursion method

    Hi,

    I have a question about a small pathfinding problem.
    I got a 2D table which symbolize a labyrinth.
    The table only contains a ' '(white space), a 'B', a 'E' and a 'W'
    B: begin position
    E: end position
    W: wall

    I need to write out all the pads from B to E.
    (a) I may not cross a wall
    (b) I may not move to a position I have already been before. (in the same pad)

    for example I have the following labyrinth: (ignore the [])
    [M][ ][ ][ ][ ]
    [B][ ][M][ ][E]
    [M][ ][ ][ ][ ]

    My java program needs to print out ALL the possible pads from B to E:
    rurrrd
    rurrdr
    rurrddru
    rdrrru
    rdrrur
    rdrruurd

    I have written this little program.
    It's an excercice from the exam from last year and I should be able to solve it with recursion.
    But my program only print out 1 possible pad instead of ALL pads.
    If someone can point me where and what I'm doing wrong I would be verry gratefull. (I'm practicing for my upcomming exam)
    (excuse me for my bad english)

    Java Code:
    class Labyrinth{
      public static void main(String [] args){
        char [][] labyrinth = {{'W',' ',' ',' ',' '},{'B',' ','W',' ','E'},{'W',' ',' ',' ',' '}};
        pads(labyrinth);
      }
      
      
      static void pads(char [][] labyrinth){
        char [][] help = new char[labyrinth.length][labyrinth[0].length];
        int row = startingposition(labyrinth , true); 
        
        int column = startingposition(labyrinth, false); 
        
        String way= "";
        findpad(labyrinth, help, row , column, way);
      }
      
      static int startingposition(char[][] labyrinth,boolean row){
        int i,j;
        boolean found = false;
        int startingposition = 0;
        for(i=0; i <labyrinth.length && found == false; i++){
          for(j=0; j < labyrinth[i].length && found==false; j++){
            if(labyrinth[i][j]=='B'){
              found = true;
              if(row==true)
                return i;
              else
                return j;
            }
          }
        }
        return -1;
      }
    
      static void findpad(char [][] labyrinth, char [][] help, int row, int column, String way){
        int i,j;
        
        if(labyrinth[row][column]=='E'){
          System.out.println(way);
        }
      
        help[row][column]='X'; 
     
        
        if(labyrinth[row][column]!='E'){
          for(i=-1; i<=1; i++){
            for(j=-1; j<=1; j++){
              
              if(i!=j && (i==0 || j==0) && row+i>0 && column+j>0 && row+i<labyrinth.length && column+j<labyrinth[0].length && help[row+i][column+j]!='X' && labyrinth[row+i][column+j]!='W'){
                if(i>0)
                  way+="u";
                else if(i<0){
                  way+="d"; 
                }
                else if(j>0){
                  way+="r"; 
                }
                else if(j<0){
                  way+="l"; 
                }
    
                
                findpad(labyrinth,help,row+i,column+j,way);
                
              }
            }
          }
          
       
        }
        
        
      }
      
    }

  2. #2
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: Java Recursion method

    Just before it returns, shouldn't findpad() remove from help[][] the X it made?
    Last edited by 2by4; 12-16-2011 at 06:12 PM.

  3. #3
    Risvosk is offline Member
    Join Date
    Dec 2011
    Posts
    2
    Rep Power
    0

    Default Re: Java Recursion method

    If i remove the X again then i will get an endless loop. (stackoverflow)
    But i think it has definitely something to do with my help table.

  4. #4
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: Java Recursion method

    Yes, my intuition tells me that the it should place an X when if finds a blank, not from the input values

    + it should clear away however many Xs it makes just before it returns.

Similar Threads

  1. Replies: 3
    Last Post: 04-12-2011, 07:44 AM
  2. Turning Recursion Method into Iterative method
    By mattakuevan in forum New To Java
    Replies: 9
    Last Post: 06-15-2010, 07:46 AM
  3. Replies: 1
    Last Post: 03-17-2010, 06:25 AM
  4. My first recursion method: the number e
    By Lil_Aziz1 in forum Reviews / Advertising
    Replies: 1
    Last Post: 01-23-2010, 11:28 PM
  5. implement binary search method using recursion?
    By chopo1980 in forum New To Java
    Replies: 1
    Last Post: 12-12-2009, 04:58 PM

Posting Permissions

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