This content originally appeared on DEV Community and was authored by Garvit Khamesra
Question:
Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N – 1, N – 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right). Value 0 at a cell in the matrix represents that it is blocked and the rat cannot move to it while value 1 at a cell in the matrix represents that rat can travel through it.
Note: In a path, no cell can be visited more than one time.
Print the answer in lexicographical(sorted) order
Examples:
Example 1:
Input:
N = 4
m[][] = `{{1, 0, 0, 0},
{1, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 1}}`
Output: DDRDRR DRDDRR
Explanation:
The rat can reach the destination at (3, 3) from (0, 0) by two paths - DRDDRR and DDRDRR, when printed in sorted order we get DDRDRR DRDDRR.
Example 2:
Input: N = 2
m[][] = `{{1, 0},
{1, 0}}`
Output:
No path exists and the destination cell is blocked.
Solution:
After reading the question, the solution approach is straightforward:
We need to find a path in the maze so that the rat reaches the exit, to do that we just need to start from the initial point and see if we can move to the next block in any of the 4 directions.
Now comes the tricky part how we can code this solution:
By looking at the pattern of our solution we can say this will be a backtracking problem, and also we can see that we can use recursion for our solution.
My idea is to break down the code into smaller pieces so that we don’t get confused. That’s how I like to approach it.
So I’ll start by writing wrappers and the main method, basically all the pre-requisite.
1 more point, we need to find all the paths and also we should not end up visiting the nodes again and again. To handle these 2 conditions we will be using visited nodes array.
package medium.recursion.backtracking;
import java.util.ArrayList;
public class RatInAMaze {
// Main method to test our code.
public static void main(String[] args) {
int n = 4;
int[][] a = `{{1,0,0,0},{1,1,0,1},{1,1,0,0},{0,1,1,1}}`;
ArrayList< String > res = findPath(a, n);
if (res.size() > 0) {
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
System.out.println();
} else {
System.out.println(-1);
}
}
// Based on our solution we have added a new array to maintain visited nodes
private static ArrayList findPath(int[][] arr, int n) {
int visited[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = 0;
}
}
ArrayList < String > ans = new ArrayList < > ();
if (arr[0][0] == 1) {
findPathHelper(arr, n, 0, 0, ans, "", visited);
}
return ans;
}
}
Now we are ready with the test code and the method for our solution. We have defined our helper method as:
findPathHelper(int[][] arr, int n, int i, int j, ArrayList<String> allDiffPaths, String path, int[][] visited)
We are starting from 0,0 and we will be maintaining the current path and all the paths which leads to the solution.
If you haven’t gone through Code 101: Sort an Array using Recursion, please have a look at the Recursive Algorithm explained here.
Now as we know we can solve this with recursion, we will try to think of a base condition.
Base Condition:
We know that once the rat reaches the end of the maze it’s a success and we add it to our solution.
Now skipping the second point Work needed to move toward Base Case or Solution and moving towards 3rd point the Recursive Call (call ourselves)
As we know the rat can move in 4 directions, so the recursive call corresponding will be
findPathHelper(arr, n, i+1, j, ans, path + "D", visited); findPathHelper(arr, n, i-1, j, ans, path + "U", visited); findPathHelper(arr, n, i, j+1, ans, path + "R", visited); findPathHelper(arr, n, i, j-1, ans, path + "L", visited); // Each call is based on each direction and that will be added in path.
Now coming to 2nd point Work needed to move toward Base Case or Solution.
We know that the calls we specified above will be called and the solution will arrive, but there are a few constraints we need to put.
- the indices should not be out of bounds
- do not visit already visited node
- skip the node if it have 0
- mark the node visited once the rat is at that node
- once you have a path make the visited node as 0 so for the next path you will have the node as not visited
We will write our helper function now:
private static void findPathHelper(int[][] arr, int n, int i, int j, ArrayList ans, String path, int[][] visited) {
if (i == n-1 && j == n-1) {
ans.add(path);
return;
}
if (visited[i][j] == 1 || arr[i][j] != 1) {
return;
}
visited[i][j] = 1;
if (i >= 0 && i + 1 < n && arr[i+1][j] == 1 && visited[i+1][j] != 1) {
findPathHelper(arr, n, i+1, j, ans, path + "D", visited);
}
if (i - 1 >= 0 && i < n && arr[i-1][j] == 1 && visited[i-1][j] != 1) {
findPathHelper(arr, n, i-1, j, ans, path + "U", visited);
}
if (j >= 0 && j+1 < n && arr[i][j+1] == 1 && visited[i][j+1] != 1) {
findPathHelper(arr, n, i, j+1, ans, path + "R", visited);
}
if (j-1 >= 0 && j < n && arr[i][j-1] == 1 && visited[i][j-1] != 1) {
findPathHelper(arr, n, i, j-1, ans, path + "L", visited);
}
visited[i][j] = 0;
}
}
This will take care of all the scenarios discussed and now consolidate everything into 1 place.
package medium.recursion.backtracking;
import java.util.ArrayList;
public class RatInAMaze {
public static void main(String[] args) {
int n = 4;
int[][] a = `{{1,0,0,0},{1,1,0,1},{1,1,0,0},{0,1,1,1}}`;
ArrayList< String > res = findPath(a, n);
if (res.size() > 0) {
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
System.out.println();
} else {
System.out.println(-1);
}
}
private static ArrayList findPath(int[][] arr, int n) {
int visited[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = 0;
}
}
ArrayList < String > ans = new ArrayList < > ();
if (arr[0][0] == 1) {
findPathHelper(arr, n, 0, 0, ans, "", visited);
}
return ans;
}
private static void findPathHelper(int[][] arr, int n, int i, int j, ArrayList ans, String path, int[][] visited) {
if (i == n-1 && j == n-1) {
ans.add(path);
return;
}
if (visited[i][j] == 1 || arr[i][j] != 1) {
return;
}
visited[i][j] = 1;
if (i >= 0 && i + 1 < n && arr[i+1][j] == 1 && visited[i+1][j] != 1) {
findPathHelper(arr, n, i+1, j, ans, path + "D", visited);
}
if (i - 1 >= 0 && i < n && arr[i-1][j] == 1 && visited[i-1][j] != 1) {
findPathHelper(arr, n, i-1, j, ans, path + "U", visited);
}
if (j >= 0 && j+1 < n && arr[i][j+1] == 1 && visited[i][j+1] != 1) {
findPathHelper(arr, n, i, j+1, ans, path + "R", visited);
}
if (j-1 >= 0 && j < n && arr[i][j-1] == 1 && visited[i][j-1] != 1) {
findPathHelper(arr, n, i, j-1, ans, path + "L", visited);
}
visited[i][j] = 0;
}
}
Now that we have completed the code, I wanted to organize it better and removed pieces that we can remove.
private static void findPathHelper(int[][] arr, int n, int i, int j, ArrayList ans, String path) {
if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 0 || arr[i][j] == -1) {
return;
}
if (i == n-1 && j == n-1) {
ans.add(path);
return;
}
arr[i][j] = -1;
findPathHelper(arr, n, i+1, j, ans, path + "D");
findPathHelper(arr, n, i-1, j, ans, path + "U");
findPathHelper(arr, n, i, j+1, ans, path + "R");
findPathHelper(arr, n, i, j-1, ans, path + "L");
arr[i][j] = 1;
}
#HappyCoding
This content originally appeared on DEV Community and was authored by Garvit Khamesra