BackTrackingAssignment

amitsen01ei

Oct 9th, 2023

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 1.92 KB | Source Code | 0 0

raw download clone embed print report

public class RatInAMaze {
private static final int[] dx = {0, 1, 0, -1};
private static final int[] dy = {1, 0, -1, 0};
private static boolean isSafeToTravel(int[][] m, int x, int y, int n, boolean[][] visited) {
return x >= 0 && y >= 0
&& x < n && y < n
&& m[x][y] == 1 && !visited[x][y];
}
/**
* Finds if there's a path from the source (0,0) to the destination (N-1,N-1).
* Time complexity: O(N^2) in the worst case.
* Space complexity: O(N^2) due to the visited matrix.
*
* @param maze The maze represented as a matrix.
* @param x The present x co-ordinate
* @param y The present y co-ordinate
* @param n The size of the matrix.
* @param visited A matrix indicating the cells that have been visited.
* @return true if a path exists, false otherwise.
*/
private static boolean traverse(int[][] maze, int x, int y, int n, boolean[][] visited) {
if (x == n - 1 && y == n - 1) {
return true;
}
visited[x][y] = true;
for (var i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (isSafeToTravel(maze, newX, newY, n, visited)) {
if (traverse(maze, newX, newY, n, visited)) {
return true;
}
}
}
visited[x][y] = false;
return false;
}
/**
* The public caller function to check if a path exists
* @param matrix The matrix needed to be traversed
* @param n The size of the n x n matrix
* @return true if a path exists, otherwise false
*/
public static boolean hasPath(int[][] matrix, int n) {
var visited = new boolean[n][n];
if (matrix[0][0] == 0) {
return false;
}
return traverse(matrix, 0, 0, n, visited);
}
}

Add Comment

Please, Sign In to add comment