1. Member
Join Date
Dec 2011
Posts
2
Rep Power
0

## 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)

Java Code:
```class Labyrinth{
public static void main(String [] args){
char [][] labyrinth = {{'W',' ',' ',' ',' '},{'B',' ','W',' ','E'},{'W',' ',' ',' ',' '}};
}

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";
}

}
}
}

}

}

}```

2. Banned
Join Date
Dec 2011
Posts
143
Rep Power
0

## 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 05:12 PM.

3. Member
Join Date
Dec 2011
Posts
2
Rep Power
0

## 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. Banned
Join Date
Dec 2011
Posts
143
Rep Power
0

## 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.

#### Posting Permissions

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