Java Recursion method

• 12-16-2011, 05:42 PM
Risvosk
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.
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)

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);                       }         }       }             }           }   }```
• 12-16-2011, 06:09 PM
2by4
Re: Java Recursion method
Just before it returns, shouldn't findpad() remove from help[][] the X it made?
• 12-16-2011, 06:18 PM
Risvosk
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.
• 12-16-2011, 06:30 PM
2by4
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.