Overheadms Overheadms - 6 months ago 32
Java Question

How can I modify this Java code (maze algorithm)

The code is a public maze algorithm so it's not mine. It's used to find a path from x to y.

As an example, we got input:

{{1, 1, 0, 1},
{0, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1}
};


The output will be:

1 1 0 0
0 1 0 0
0 1 0 0
0 1 1 1


As we can see, it will start from top left corner and end in bottom right corner.
My question, how can I change the code so it starts from bottom left and ends in top right corner instead?
I have tried many things but the output was always
Solution doesn't exist
: /

I think the only method that requires changes for this is
boolean solveMazeUtil

I need this code for something else but it needs modification and this is my problem here...
Also I can only go up and right but this algorithm does it little different, it goes right and down.
I hope I could explain my problem good?
Tyvm for all

Complete code:

public class CatMouse
{
final int N = 4;

/* A utility function to print solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] +
" ");
System.out.println();
}
}

/* A utility function to check if x,y is valid
index for N*N maze */
boolean isSafe(int maze[][], int x, int y)
{
// if (x,y outside maze) return false
return (x >= 0 && x < N && y >= 0 &&
y < N && maze[x][y] == 1);
}

/* This function solves the Maze problem using
Backtracking. It mainly uses solveMazeUtil()
to solve the problem. It returns false if no
path is possible, otherwise return true and
prints the path in the form of 1s. Please note
that there may be more than one solutions, this
function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int sol[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

if (solveMazeUtil(maze, 0, 0, sol) == false)
{
System.out.print("Solution doesn't exist");
return false;
}

printSolution(sol);
return true;
}

/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x,y is goal) return true
if (x == N - 1 && y == N - 1)
{
sol[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;

/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;

/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;

/* If none of the above movements work then
BACKTRACK: unmark x,y as part of solution
path */
sol[x][y] = 0;
return false;
}

return false;
}

public static void main(String args[])
{
CatMouse rat = new CatMouse();
int maze[][] = {{1, 1, 0, 1},
{0, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1}
};
rat.solveMaze(maze);
}
}
// This code is contributed by Abhishek Shankhadhar

Answer

You basically have to do 3 changes:

  1. Change starting position
  2. Change the check to see if we arrived at the destination
  3. Change the legal moves from right and down to right and up

1.

In solveMaze(int maze[][])

you have the line

if (solveMazeUtil(maze, 0, 0, sol) == false)

Here it is where you are saying "start at the top left corner" (0, 0)

Change it so you to start at the bottom left (0, N-1):

if (solveMazeUtil(maze, 0, N-1, sol) == false)

2.

You want to reach the top right corner. The check to see if we arrived at the end is in this line:

if (x == N - 1 && y == N - 1) 

Here it is checking for bottom right which is: (N-1, N-1). Top right would be (N-1, 0). So you should change that line to:

if (x == N - 1 && y == 0)

3.

you can only move up and right instead of down and right. Thus we don't have to change the "right" part. What we have to change is the "down" to "up".

Moving down happens here:

/* If moving in x direction doesn't give
solution then  Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
    return true;

This is where you the recursion goes "down" rather than up. Change it to:

/* If moving in x direction doesn't give
solution then  Move up in y direction */
if (solveMazeUtil(maze, x, y - 1, sol))
    return true;

I might still be missing something, but from the quick look I had at it, I'd say these changes should pretty much do the trick.