Rat in a Maze
We have discussed Backtracking and Knight’s tour problem in Set 1. Let us discuss Rat in a Maze as another example problem that can be solved using Backtracking.
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 rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it. Return the list of paths in lexicographically increasing order.
Note: In a path, no cell can be visited more than one time. If the source cell is 0, the rat cannot move to any other cell.
Example:
Input:
Output: DRDDRR
Explanation:
Rat in a Maze using Backtracking:
We use a backtracking algorithm to explore all possible paths. While exploring the paths we keep track of the directions we have moved so far and when we reach to the bottom right cell, we record the path in a vector of strings.
Step-by-step approach:
- Create isValid() function to check if a cell at position (row, col) is inside the maze and unblocked.
- Create findPath() to get all valid paths:
- Base case: If the current position is the bottom-right cell, add the current path to the result and return.
- Mark the current cell as blocked.
- Iterate through all possible directions.
- Calculate the next position based on the current direction.
- If the next position is valid (i.e, if isValid() return true), append the direction to the current path and recursively call the findPath() function for the next cell.
- Backtrack by removing the last direction from the current path.
- Mark the current cell as unblocked before returning.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Initialize a string direction which represents all the
// directions.
string direction = "DLRU";
// Arrays to represent change in rows and columns
int dr[4] = { 1, 0, 0, -1 };
int dc[4] = { 0, -1, 1, 0 };
// Function to check if cell(row, col) is inside the maze
// and unblocked
bool isValid(int row, int col, int n, vector<vector<int> >& maze)
{
return row >= 0 && col >= 0 && row < n && col < n
&& maze[row][col];
}
// Function to get all valid paths
void findPath(int row, int col, vector<vector<int> >& maze,
int n, vector<string>& ans,
string& currentPath)
{
// If we reach the bottom right cell of the matrix, add
// the current path to ans and return
if (row == n - 1 && col == n - 1) {
ans.push_back(currentPath);
return;
}
// Mark the current cell as blocked
maze[row][col] = 0;
for (int i = 0; i < 4; i++) {
// Find the next row based on the current row (row)
// and the dr[] array
int nextrow = row + dr[i];
// Find the next column based on the current column
// (col) and the dc[] array
int nextcol = col + dc[i];
// Check if the next cell is valid or not
if (isValid(nextrow, nextcol, n, maze)) {
currentPath += direction[i];
// Recursively call the FindPath function for
// the next cell
findPath(nextrow, nextcol, maze, n, ans,
currentPath);
// Remove the last direction when backtracking
currentPath.pop_back();
}
}
// Mark the current cell as unblocked
maze[row][col] = 1;
}
int main()
{
vector<vector<int> > maze = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 } };
int n = maze.size();
// vector to store all the valid paths
vector<string> result;
// Store current path
string currentPath = "";
if (maze[0][0] != 0 && maze[n - 1][n - 1] != 0) {
// Function call to get all valid paths
findPath(0, 0, maze, n, result, currentPath);
}
if (result.size() == 0)
cout << -1;
else
for (int i = 0; i < result.size(); i++)
cout << result[i] << " ";
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class MazePaths {
// Initialize a string direction which represents all
// the directions.
static String direction = "DLRU";
// Arrays to represent change in rows and columns
static int[] dr = { 1, 0, 0, -1 };
static int[] dc = { 0, -1, 1, 0 };
// Function to check if cell(row, col) is inside the
// maze and unblocked
static boolean isValid(int row, int col, int n,
int[][] maze)
{
return row >= 0 && col >= 0 && row < n && col < n
&& maze[row][col] == 1;
}
// Function to get all valid paths
static void findPath(int row, int col, int[][] maze,
int n, ArrayList<String> ans,
StringBuilder currentPath)
{
// If we reach the bottom right cell of the matrix,
// add the current path to ans and return
if (row == n - 1 && col == n - 1) {
ans.add(currentPath.toString());
return;
}
// Mark the current cell as blocked
maze[row][col] = 0;
for (int i = 0; i < 4; i++) {
// Find the next row based on the current row
// (row) and the dr[] array
int nextrow = row + dr[i];
// Find the next column based on the current
// column (col) and the dc[] array
int nextcol = col + dc[i];
// Check if the next cell is valid or not
if (isValid(nextrow, nextcol, n, maze)) {
currentPath.append(direction.charAt(i));
// Recursively call the FindPath function
// for the next cell
findPath(nextrow, nextcol, maze, n, ans,
currentPath);
// Remove the last direction when
// backtracking
currentPath.deleteCharAt(
currentPath.length() - 1);
}
}
// Mark the current cell as unblocked
maze[row][col] = 1;
}
public static void main(String[] args)
{
int[][] maze = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 } };
int n = maze.length;
// List to store all the valid paths
ArrayList<String> result = new ArrayList<>();
// Store current path
StringBuilder currentPath = new StringBuilder();
if (maze[0][0] != 0 && maze[n - 1][n - 1] != 0) {
// Function call to get all valid paths
findPath(0, 0, maze, n, result, currentPath);
}
if (result.size() == 0)
System.out.println(-1);
else
for (String path : result)
System.out.print(path + " ");
System.out.println();
}
}
# Initialize a string direction which represents all the directions.
direction = "DLRU"
# Arrays to represent change in rows and columns
dr = [1, 0, 0, -1]
dc = [0, -1, 1, 0]
# Function to check if cell(row, col) is inside the maze
# and unblocked
def is_valid(row, col, n, maze):
return 0 <= row < n and 0 <= col < n and maze[row][col] == 1
# Function to get all valid paths
def find_path(row, col, maze, n, ans, current_path):
# If we reach the bottom right cell of the matrix, add
# the current path to ans and return
if row == n - 1 and col == n - 1:
ans.append(current_path)
return
# Mark the current cell as blocked
maze[row][col] = 0
for i in range(4):
# Find the next row based on the current row (row)
# and the dr[] array
next_row = row + dr[i]
# Find the next column based on the current column
# (col) and the dc[] array
next_col = col + dc[i]
# Check if the next cell is valid or not
if is_valid(next_row, next_col, n, maze):
current_path += direction[i]
# Recursively call the find_path function for
# the next cell
find_path(next_row, next_col, maze, n, ans, current_path)
# Remove the last direction when backtracking
current_path = current_path[:-1]
# Mark the current cell as unblocked
maze[row][col] = 1
# Driver code
maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 0, 0],
[0, 1, 1, 1]
]
n = len(maze)
# List to store all the valid paths
result = []
# Store current path
current_path = ""
if maze[0][0] != 0 and maze[n - 1][n - 1] != 0:
# Function call to get all valid paths
find_path(0, 0, maze, n, result, current_path)
if not result:
print(-1)
else:
print(" ".join(result))
using System;
using System.Collections.Generic;
public class Program
{
// Initialize an array to represent the change in rows and columns
static int[] dr = { 1, 0, 0, -1 };
static int[] dc = { 0, -1, 1, 0 };
static string direction = "DLRU";
// Function to check if cell (row, col) is inside the maze and unblocked
static bool IsValid(int row, int col, int n, int[,] maze)
{
return row >= 0 && col >= 0 && row < n && col < n && maze[row, col] == 1;
}
// Function to get all valid paths
static void FindPath(int row, int col, int[,] maze, int n, List<string> ans, ref string currentPath)
{
// If we reach the bottom right cell of the matrix, add the current path to ans and return
if (row == n - 1 && col == n - 1)
{
ans.Add(currentPath);
return;
}
// Mark the current cell as blocked
maze[row, col] = 0;
for (int i = 0; i < 4; i++)
{
// Find the next row based on the current row (row) and the dr[] array
int nextrow = row + dr[i];
// Find the next column based on the current column (col) and the dc[] array
int nextcol = col + dc[i];
// Check if the next cell is valid or not
if (IsValid(nextrow, nextcol, n, maze))
{
currentPath += direction[i];
// Recursively call the FindPath function for the next cell
FindPath(nextrow, nextcol, maze, n, ans, ref currentPath);
// Remove the last direction when backtracking
currentPath = currentPath.Remove(currentPath.Length - 1);
}
}
// Mark the current cell as unblocked
maze[row, col] = 1;
}
public static void Main()
{
int[,] maze = {
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 }
};
int n = maze.GetLength(0);
// List to store all the valid paths
List<string> result = new List<string>();
// Store current path
string currentPath = "";
if (maze[0, 0] != 0 && maze[n - 1, n - 1] != 0)
{
// Function call to get all valid paths
FindPath(0, 0, maze, n, result, ref currentPath);
}
if (result.Count == 0)
Console.WriteLine(-1);
else
foreach (string path in result)
Console.Write(path + " ");
Console.WriteLine();
}
}
// Initialize a string direction which represents all the directions.
const direction = "DLRU";
// Arrays to represent change in rows and columns
const dr = [1, 0, 0, -1];
const dc = [0, -1, 1, 0];
// Function to check if cell(row, col) is inside the maze
// and unblocked
function isValid(row, col, n, maze) {
return row >= 0 && col >= 0 && row < n && col < n
&& maze[row][col] === 1;
}
// Function to get all valid paths
function findPath(row, col, maze, n, ans, currentPath) {
// If we reach the bottom right cell of the matrix, add
// the current path to ans and return
if (row === n - 1 && col === n - 1) {
ans.push(currentPath);
return;
}
// Mark the current cell as blocked
maze[row][col] = 0;
for (let i = 0; i < 4; i++) {
// Find the next row based on the current row (row)
// and the dr[] array
const nextrow = row + dr[i];
// Find the next column based on the current column
// (col) and the dc[] array
const nextcol = col + dc[i];
// Check if the next cell is valid or not
if (isValid(nextrow, nextcol, n, maze)) {
currentPath += direction[i];
// Recursively call the findPath function for
// the next cell
findPath(nextrow, nextcol, maze, n, ans, currentPath);
// Remove the last direction when backtracking
currentPath = currentPath.slice(0, -1);
}
}
// Mark the current cell as unblocked
maze[row][col] = 1;
}
// Driver code
const maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 0, 0],
[0, 1, 1, 1]
];
const n = maze.length;
// Array to store all the valid paths
const result = [];
// Store current path
let currentPath = "";
if (maze[0][0] !== 0 && maze[n - 1][n - 1] !== 0) {
// Function call to get all valid paths
findPath(0, 0, maze, n, result, currentPath);
}
if (result.length === 0)
console.log(-1);
else
console.log(result.join(" "));
Output
DDRDRR DRDDRR
Time Complexity: O(3^(m*n)), because on every cell we have to try 3 different directions.
Auxiliary Space: O(m*n), Maximum Depth of the recursion tree(auxiliary space).
Contact Us