recently I've been trying to work on some recursive maze code that returns the shortest path in a maze. If there is no path through the maze, then the code would return -1.
For example, for the board:
W-S-
----
--X-
Where S is the start of the maze, W represents a wall, X represents the desired destination, and - represents an available path point.
The output would be: 2
For the board:
-SW
-W-
W-X
the output would be -1
This is all carried out through a board class that takes a string and the dimensions of a maze, a check function that returns the shortest path, and a win function that returns the shortest path or -1 if there is no path. However, when I run my code, I'm getting an output of negative 1 for the first example and an output of 1 for the second example.
My code:
Board Class:
class Board
{
private char[][] board;
private int maxPath = 9999;
public Board(int rows, int cols, String line)
{
char[][] board1 = new char[rows][cols];
int z = 0;
for(int x = 0; x < rows; x++) {
for(int y = 0; y < cols; y++) {
board1[x][y] = line.charAt(z);
z++;
}
}
board = board1;
}
/** returns the length of the longest possible path in the Board */
public int getMaxPath()
{
return maxPath;
}
public void display()
{
if(board==null)
return;
System.out.println();
for(int a = 0; a<board.length; a++)
{
for(int b = 0; b<board[0].length; b++)
{
System.out.print(board[a][b]);
}
System.out.println();
}
}
/**
* calculates and returns the shortest path from S to X, if it exists
* @param r is the row of "S"
* @param c is the column of "S"
*/
public int check(int r, int c)
{
if(r<0||r > board.length-1||c<0||c>board[0].length-1) {
return maxPath;
}
if(board[r][c] == '*') {
return maxPath;
}
if(board[r][c] == 'W') {
return maxPath;
}
if(board[r][c] == 'X') {
return 0;
}
if(board[r][c] == '-') {
board[r][c] = '*';
}
int up = 1 + check(r-1,c);
int down = 1 + check(r+1,c);
int left = 1 + check(r,c-1);
int right = 1 + check(r,c+1);
board[r][c] = '-';
if(up < down) {
if(up < left) {
if(up < right) {
return up;
}
else {
return right;
}
}
else {
if(left < right) {
return left;
}
else {
return right;
}
}
}
else {
if(down < left) {
if(down < right) {
return down;
}
else {
return right;
}
}
else {
if(left < right) {
return left;
}
else {
return right;
}
}
}
}
/**
* precondition: S and X exist in board
* postcondition: returns either the length of the path
* from S to X, or -1, if no path exists.
*/
public int win()
{
int x = 0;
int y = 0;
int z = 0;
int startRow = 0;
int startCol = 0;
while( x < board.length && z == 0) {
while(y < board[0].length && z == 0) {
if(board[x][y] == 'S') {
z++;
startRow = x;
startCol = y;
}
y++;
}
x++;
}
System.out.println(startRow + " " + startCol);
if(check(startRow,startCol) < maxPath) {
return check(startRow,startCol);
}
else if (check(startRow,startCol) == maxPath) {
return 1;
}
else {
return -1;
}
}
Test cases:
public static void main(String[] args)
{
Board b = null;
b = new Board(3,4,"W-S-------X-");
b.display();
System.out.println("Shortest path is " + b.win()); //2
b = new Board(4,3,"S-W-----X-W-");
b.display();
System.out.println("Shortest path is " + b.win()); //4
b = new Board(3,4,"X-WS--W-W---");
b.display();
System.out.println("Shortest path is " + b.win()); //7
b = new Board(3,5,"W--WW-X----SWWW");
b.display();
System.out.println("Shortest path is " + b.win()); //1
b = new Board(3,3,"-SW-W-W-X"); //no path exists
b.display();
System.out.println("Shortest path is " + b.win()); //-1
b = new Board(5,7,"-W------W-W-WX--S----W----W-W--W---"); //Example Board 1
b.display();
System.out.println("Shortest path is " + b.win()); //5
b = new Board(4,4,"-WX--W-W-WW-S---"); //Example Board -1
b.display();
System.out.println("Shortest path is " + b.win()); //5
//what other test cases should you test?
}
Desired outputs:
W-S-
----
--X-
Shortest path is 2
S-W
---
--X
-W-
Shortest path is 4
X-WS
--W-
W---
Shortest path is 7
W--WW
-X---
-SWWW
Shortest path is 1
-SW
-W-
W-X
Shortest path is -1
-W-----
-W-W-WX
--S----
W----W-
W--W---
Shortest path is 5
-WX-
-W-W
-WW-
S---
Shortest path is -1
My wrong outputs:
W-S-
----
--X-
Shortest path is -1
S-W
---
--X
-W-
Shortest path is 1
X-WS
--W-
W---
Shortest path is -1
W--WW
-X---
-SWWW
Shortest path is -1
-SW
-W-
W-X
Shortest path is 1
-W-----
-W-W-WX
--S----
W----W-
W--W---
Shortest path is 1
-WX-
-W-W
-WW-
S---
Shortest path is 1
My new mostly right outputs:
W-S-
----
--X-
0 2
Shortest path is 2
S-W
---
--X
-W-
0 0
Shortest path is 4
X-WS
--W-
W---
0 3
Shortest path is 7
W--WW
-X---
-SWWW
0 0
Shortest path is 1
-SW
-W-
W-X
0 1
Shortest path is -1
-W-----
-W-W-WX
--S----
W----W-
W--W---
0 0
Shortest path is 9
-WX-
-W-W
-WW-
S---
0 0
Shortest path is -1
Can someone explain what I am doing wrong(just between my new outputs and the desired outputs) and how I can fix it?
EDIT: Thank you peter and mrB, I have implemented your suggestions and updated my code to fit that!
It looks like there are 2 issues with your code.
First, the while loops in your win() function will leave your starting position at the top left of your boards.
z == 0 which means that z > 0 is false and the while loop will not be used.x or y, so it's good that the z condition fails or you'd have infinite loops.Second, maxPath is never assigned a value. Making it 0 and all results that go out of bounds (I'm thinking the first up) become the result of check(x,y) as it's 1 + 0. The -1 results are all when the top left of the board is 'W' or 'X' in which case check(x,y) returns 0 which is equal to maxPath
You might also want to set check(x,y) to a int rather than calling it again to return a result (bigger boards could become a bit resource intensive).
In summary
z == 0 and increment x and y respectively.maxPath to a value, e.g. 9999win() to check that result of check(x,y) is < maxPath (otherwise you might not get a -1 result out of win() because there is a possibility that maxPath will be incremented by 1 or more and != maxPath would result in true).