Two Rats in a Maze
Given a 2D matrix maze[][], where some cells are blocked, some cells are locked (which the rats can unlock) and some cells are vacant. Given the initial position of two rats, find the minimum number of cells they need to unlock to escape the maze. A rat can escape the maze if it reaches outside the boundary of the maze. Blocked cells are represented by ‘*’, locked cells are represented by ‘#’, vacant cells are represented by ‘.’, and the initial position of rats is represented by ‘$’. A path from the outside to that rat is guaranteed to exist for each rat.
Note: If a rat unlocks a cell, it remains unlocked. A rat cannot pass through blocked cells and can pass through locked cells after unlocking them. Add images to represent the problem.
Example:
Input: n = 5, m = 9,
inputMaze[5][10] = { ****#****
*..#.#..*
****.****
*$#.#.#$*
*********}
Output: 4Input: n = 5, m = 11
inputMaze = {*#*********
*$*…*…*
*$*.*.*.*.*
*…*…*.*
*********.*}
Output: 0
Approach:
The idea is to first initializes distances from the outside boundary and rats’ initial positions using breadth-first search (BFS). It then identifies and stores the positions of the locked cells. The BFS is performed for each rat separately, updating distances and considering the unlocking of doors. The final answer is calculated by adding the distances of both rats and the initial distances, adjusting for the unlocking of shared doors. The result represents the minimum number of cells that both rats need to unlock to escape the maze.
Steps:
- Initialization:
- The maze is represented as a 2D grid (maze[][]).
- The rats’ initial positions are marked with ‘$’, blocked cells with ‘*’, locked cells with ‘#’, and vacant cells with ‘.’.
- BFS for Initial Cells:
- Initialize the distances from the outside boundary to the initial cells with money (‘$’) and doors (‘#’).
- Perform a breadth-first search (BFS) from the border cells with money (‘$’) and doors (‘#’).
- Update the distances as the BFS progresses.
- Identification of Rats and Locked Cells:
- Identify the positions of the two rats and collect the positions of unlocked doors (‘#’).
- DFS and BFS for Rats and Unlocked Doors:
- Perform depth-first search (DFS) and breadth-first search (BFS) to calculate the distances from the outside boundary to each rat and the distances from each rat to every unlocked door.
- Update the distances during the searches.
- Calculation of Minimum Cells to Unlock:
- Calculate the minimum number of cells the rats need to unlock to escape by considering their individual distances and the initial distances from the outside boundary.
- Iterate through the positions of unlocked doors and update the answer based on the sum of distances from both rats to the door and subtracting the initial distances (accounting for the fact that each door is unlocked by both rats).
- Final Answer:
- The final answer represents the minimum number of cells the two rats need to unlock collectively to successfully escape the maze.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> #define MAXN 105 #define INF 0x3f3f3f3f using namespace std; char maze[MAXN][MAXN]; int n, m; int distanceFromStart[MAXN * MAXN], distanceFromRat1[MAXN * MAXN], distanceFromRat2[MAXN * MAXN]; bool visited[MAXN][MAXN]; vector< int > unlockedCells; queue< int > Q; const int step[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 }; // Function to perform depth-first search void dfs( int x, int y, int d, int * distance) { // Iterate through all possible directions for ( int i = 0; i < 4; i++) { int u = x + step[i][0]; int v = y + step[i][1]; // Skip visited cells, obstacles, and out-of-bounds // cells if (visited[u][v] || maze[u][v] == '*' || u < 0 || v < 0 || u >= n || v >= m) continue ; distance[m * u + v] = d; visited[u][v] = true ; // If the cell is a door, increment the distance and // add to the queue if (maze[u][v] == '#' ) { distance[m * u + v]++; Q.push(m * u + v); } else { dfs(u, v, d, distance); } } } // Function to perform breadth-first search void bfs( int * distance) { while (!Q.empty()) { int p = Q.front(); int x = p / m, y = p % m; Q.pop(); // DFS at one time is equivalent to the price plus // one dfs(x, y, distance[m * x + y], distance); } } int main() { int T = 1; while (T--) { // Input n = 5; m = 9; char inputMaze[5][10] = { "****#****", "*..#.#..*", "****.****", "*$#.#.#$*", "*********" }; for ( int i = 0; i < n; i++) { strcpy (maze[i], inputMaze[i]); } memset (distanceFromStart, INF, sizeof (distanceFromStart)); memset (distanceFromRat1, INF, sizeof (distanceFromRat1)); memset (distanceFromRat2, INF, sizeof (distanceFromRat2)); memset (visited, 0, sizeof (visited)); unlockedCells.clear(); bool isRat1Found = false ; int rat1Pos = 0, rat2Pos = 0; // Initialization and BFS for initial cells for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Add border cells and cells with money to // the queue if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && (maze[i][j] == '.' || maze[i][j] == '$' )) { Q.push(m * i + j); distanceFromStart[m * i + j] = 0; visited[i][j] = true ; } } } // Identifying rats and locked cells for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Skip obstacles if (maze[i][j] == '*' ) continue ; // If it's a door on the border, mark it as // visited and set the initial distance if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && maze[i][j] == '#' ) { distanceFromStart[m * i + j] = 1; Q.push(m * i + j); visited[i][j] = true ; } // Collect unlocked doors if (maze[i][j] == '#' ) { unlockedCells.push_back(m * i + j); } // Identify rat positions if (maze[i][j] == '$' ) { if (!isRat1Found) { rat1Pos = m * i + j; distanceFromRat1[rat1Pos] = 0; isRat1Found = true ; } else { rat2Pos = m * i + j; distanceFromRat2[rat2Pos] = 0; } } } } // Perform BFS for the initial cells bfs(distanceFromStart); // Clear visited array for the next BFS memset (visited, 0, sizeof (visited)); visited[rat1Pos / m][rat1Pos % m] = true ; Q.push(rat1Pos); // Perform BFS for rat 1 bfs(distanceFromRat1); // Clear visited array for the next BFS memset (visited, 0, sizeof (visited)); visited[rat2Pos / m][rat2Pos % m] = true ; Q.push(rat2Pos); // Perform BFS for rat 2 bfs(distanceFromRat2); // Calculate the final answer int ans = distanceFromStart[rat1Pos] + distanceFromStart[rat2Pos]; for ( int i = 0; i < unlockedCells.size(); i++) { // Update the answer by considering the rats' // distances and initial distances ans = min( ans, distanceFromRat1[unlockedCells[i]] + distanceFromRat2[unlockedCells[i]] + distanceFromStart[unlockedCells[i]] - 2); } printf ("%d\n", ans); } return 0; } |
Java
import java.util.*; public class Main { static final int MAXN = 105 ; static final int INF = 0x3f3f3f3f ; static char [][] maze = new char [MAXN][MAXN]; static int n, m; static int [] distanceFromStart = new int [MAXN * MAXN]; static int [] distanceFromRat1 = new int [MAXN * MAXN]; static int [] distanceFromRat2 = new int [MAXN * MAXN]; static boolean [][] visited = new boolean [MAXN][MAXN]; static List<Integer> unlockedCells = new ArrayList<>(); static Queue<Integer> Q = new LinkedList<>(); static final int [][] step = { { 1 , 0 }, { 0 , 1 }, { - 1 , 0 }, { 0 , - 1 } }; static void dfs( int x, int y, int d, int [] distance) { // Iterate through all possible directions for ( int i = 0 ; i < 4 ; i++) { int u = x + step[i][ 0 ]; int v = y + step[i][ 1 ]; // Check if the new coordinates are within // bounds if (u >= 0 && v >= 0 && u < n && v < m) { // Skip visited cells, obstacles, and // out-of-bounds cells if (visited[u][v] || maze[u][v] == '*' || maze[u][v] == '$' ) { continue ; } distance[m * u + v] = d; visited[u][v] = true ; // If the cell is a door, increment the // distance and add to the queue if (maze[u][v] == '#' ) { distance[m * u + v]++; Q.add(m * u + v); } else { dfs(u, v, d, distance); } } } } // Function to perform breadth-first search static void bfs( int [] distance) { while (!Q.isEmpty()) { int p = Q.poll(); int x = p / m, y = p % m; // DFS at one time is equivalent to the price // plus one dfs(x, y, distance[m * x + y], distance); } } public static void main(String[] args) { int T = 1 ; while (T-- > 0 ) { // Input n = 5 ; m = 9 ; char [][] inputMaze = { "****#****" .toCharArray(), "*..#.#..*" .toCharArray(), "****.****" .toCharArray(), "*$#.#.#$*" .toCharArray(), "*********" .toCharArray() }; for ( int i = 0 ; i < n; i++) { maze[i] = Arrays.copyOf(inputMaze[i], m); } Arrays.fill(distanceFromStart, INF); Arrays.fill(distanceFromRat1, INF); Arrays.fill(distanceFromRat2, INF); for ( boolean [] row : visited) { Arrays.fill(row, false ); } unlockedCells.clear(); boolean isRat1Found = false ; int rat1Pos = 0 , rat2Pos = 0 ; // Initialization and BFS for initial cells for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // Add border cells and cells with money // to the queue if ((i == 0 || j == 0 || i == n - 1 || j == m - 1 ) && (maze[i][j] == '.' || maze[i][j] == '$' )) { Q.add(m * i + j); distanceFromStart[m * i + j] = 0 ; visited[i][j] = true ; } } } // Identifying rats and locked cells for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // Skip obstacles if (maze[i][j] == '*' ) continue ; // If it's a door on the border, mark it // as visited and set the initial // distance if ((i == 0 || j == 0 || i == n - 1 || j == m - 1 ) && maze[i][j] == '#' ) { distanceFromStart[m * i + j] = 1 ; Q.add(m * i + j); visited[i][j] = true ; } // Collect unlocked doors if (maze[i][j] == '#' ) { unlockedCells.add(m * i + j); } // Identify rat positions if (maze[i][j] == '$' ) { if (!isRat1Found) { rat1Pos = m * i + j; distanceFromRat1[rat1Pos] = 0 ; isRat1Found = true ; } else { rat2Pos = m * i + j; distanceFromRat2[rat2Pos] = 0 ; } } } } // Perform BFS for the initial cells bfs(distanceFromStart); // Clear visited array for the next BFS for ( boolean [] row : visited) { Arrays.fill(row, false ); } visited[rat1Pos / m][rat1Pos % m] = true ; Q.add(rat1Pos); // Perform BFS for rat 1 bfs(distanceFromRat1); // Clear visited array for the next BFS for ( boolean [] row : visited) { Arrays.fill(row, false ); } visited[rat2Pos / m][rat2Pos % m] = true ; Q.add(rat2Pos); // Perform BFS for rat 2 bfs(distanceFromRat2); // Calculate the final answer int ans = distanceFromStart[rat1Pos] + distanceFromStart[rat2Pos]; for ( int i = 0 ; i < unlockedCells.size(); i++) { // Update the answer by considering the // rats' distances and initial distances ans = Math.min( ans, distanceFromRat1[unlockedCells.get(i)] + distanceFromRat2[unlockedCells .get(i)] + distanceFromStart[unlockedCells .get(i)] - 2 ); } System.out.println(ans); } } } |
Python3
# Python Implementation from collections import deque def dfs(x, y, d, distance): for i in range ( 4 ): u, v = x + step[i][ 0 ], y + step[i][ 1 ] if visited[u][v] or maze[u][v] = = '*' or u < 0 or v < 0 or u > = n or v > = m: continue distance[m * u + v] = d visited[u][v] = True if maze[u][v] = = '#' : distance[m * u + v] + = 1 Q.append(m * u + v) else : dfs(u, v, d, distance) def bfs(distance): while Q: p = Q.popleft() x, y = p / / m, p % m dfs(x, y, distance[m * x + y], distance) # Input n = 5 m = 9 input_maze = [ "****#****" , "*..#.#..*" , "****.****" , "*$#.#.#$*" , "*********" ] maze = [ list (row) for row in input_maze] distance_from_start = [ float ( 'inf' )] * (n * m) distance_from_rat1 = [ float ( 'inf' )] * (n * m) distance_from_rat2 = [ float ( 'inf' )] * (n * m) visited = [[ False ] * m for _ in range (n)] unlocked_cells = [] Q = deque() step = [( 1 , 0 ), ( 0 , 1 ), ( - 1 , 0 ), ( 0 , - 1 )] # Initialization and BFS for initial cells for i in range (n): for j in range (m): if (i = = 0 or j = = 0 or i = = n - 1 or j = = m - 1 ) and (maze[i][j] = = '.' or maze[i][j] = = '$' ): Q.append(m * i + j) distance_from_start[m * i + j] = 0 visited[i][j] = True # Identifying rats and locked cells is_rat1_found = False rat1_pos, rat2_pos = 0 , 0 for i in range (n): for j in range (m): if maze[i][j] = = '*' : continue if (i = = 0 or j = = 0 or i = = n - 1 or j = = m - 1 ) and maze[i][j] = = '#' : distance_from_start[m * i + j] = 1 Q.append(m * i + j) visited[i][j] = True if maze[i][j] = = '#' : unlocked_cells.append(m * i + j) if maze[i][j] = = '$' : if not is_rat1_found: rat1_pos = m * i + j distance_from_rat1[rat1_pos] = 0 is_rat1_found = True else : rat2_pos = m * i + j distance_from_rat2[rat2_pos] = 0 # Perform BFS for the initial cells bfs(distance_from_start) # Clear visited array for the next BFS visited = [[ False ] * m for _ in range (n)] visited[rat1_pos / / m][rat1_pos % m] = True Q.append(rat1_pos) # Perform BFS for rat 1 bfs(distance_from_rat1) # Clear visited array for the next BFS visited = [[ False ] * m for _ in range (n)] visited[rat2_pos / / m][rat2_pos % m] = True Q.append(rat2_pos) # Perform BFS for rat 2 bfs(distance_from_rat2) # Calculate the final answer ans = distance_from_start[rat1_pos] + distance_from_start[rat2_pos] for cell in unlocked_cells: ans = min (ans, distance_from_rat1[cell] + distance_from_rat2[cell] + distance_from_start[cell] - 2 ) print (ans) # This code is contributed by Sakshi |
C#
// C# Implementation using System; using System.Collections.Generic; public class MainClass { const int MAXN = 105; const int INF = 0x3f3f3f3f; static char [, ] maze = new char [MAXN, MAXN]; static int n, m; static int [] distanceFromStart = new int [MAXN * MAXN]; static int [] distanceFromRat1 = new int [MAXN * MAXN]; static int [] distanceFromRat2 = new int [MAXN * MAXN]; static bool [, ] visited = new bool [MAXN, MAXN]; static List< int > unlockedCells = new List< int >(); static Queue< int > Q = new Queue< int >(); static readonly int [, ] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // Depth-first search for a given position and distance static void Dfs( int x, int y, int d, int [] distance) { for ( int i = 0; i < 4; i++) { int u = x + step[i, 0]; int v = y + step[i, 1]; // Check bounds and visitable conditions if (u >= 0 && v >= 0 && u < n && v < m && !visited[u, v] && maze[u, v] != '*' && maze[u, v] != '$' ) { distance[m * u + v] = d; visited[u, v] = true ; if (maze[u, v] == '#' ) { distance[m * u + v]++; Q.Enqueue(m * u + v); } else { Dfs(u, v, d, distance); } } } } // Breadth-first search for the entire maze static void Bfs( int [] distance) { while (Q.Count > 0) { int p = Q.Dequeue(); int x = p / m, y = p % m; Dfs(x, y, distance[m * x + y], distance); } } public static void Main() { int T = 1; while (T-- > 0) { n = 5; m = 9; char [, ] inputMaze = { { '*' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '*' }, { '*' , '.' , '.' , '#' , '.' , '#' , '.' , '.' , '*' }, { '*' , '*' , '*' , '*' , '.' , '*' , '*' , '*' , '*' }, { '*' , '$' , '#' , '.' , '#' , '.' , '#' , '$' , '*' }, { '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' } }; // Copy the input maze for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { maze[i, j] = inputMaze[i, j]; } } // Initialization Array.Fill(distanceFromStart, INF); Array.Fill(distanceFromRat1, INF); Array.Fill(distanceFromRat2, INF); for ( int i = 0; i < MAXN; i++) { for ( int j = 0; j < MAXN; j++) { visited[i, j] = false ; } } unlockedCells.Clear(); bool isRat1Found = false ; int rat1Pos = 0, rat2Pos = 0; // Add initial cells to the queue for BFS for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && (maze[i, j] == '.' || maze[i, j] == '$' )) { Q.Enqueue(m * i + j); distanceFromStart[m * i + j] = 0; visited[i, j] = true ; } } } // Identify unlocked doors and rats for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (maze[i, j] == '*' ) continue ; if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && maze[i, j] == '#' ) { distanceFromStart[m * i + j] = 1; Q.Enqueue(m * i + j); visited[i, j] = true ; } if (maze[i, j] == '#' ) unlockedCells.Add(m * i + j); if (maze[i, j] == '$' ) { if (!isRat1Found) { rat1Pos = m * i + j; distanceFromRat1[rat1Pos] = 0; isRat1Found = true ; } else { rat2Pos = m * i + j; distanceFromRat2[rat2Pos] = 0; } } } } // Perform BFS for the start, rat1, and rat2 // positions Bfs(distanceFromStart); for ( int i = 0; i < MAXN; i++) for ( int j = 0; j < MAXN; j++) visited[i, j] = false ; visited[rat1Pos / m, rat1Pos % m] = true ; Q.Enqueue(rat1Pos); Bfs(distanceFromRat1); for ( int i = 0; i < MAXN; i++) for ( int j = 0; j < MAXN; j++) visited[i, j] = false ; visited[rat2Pos / m, rat2Pos % m] = true ; Q.Enqueue(rat2Pos); Bfs(distanceFromRat2); // Calculate and print the final result int ans = distanceFromStart[rat1Pos] + distanceFromStart[rat2Pos]; for ( int i = 0; i < unlockedCells.Count; i++) { ans = Math.Min( ans, distanceFromRat1[unlockedCells[i]] + distanceFromRat2[unlockedCells[i]] + distanceFromStart [unlockedCells[i]] - 2); } Console.WriteLine(ans); } } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Define the maximum dimensions for the maze and a constant infinity value const MAXN = 105; const INF = 0x3f3f3f3f; // Initialize the maze, dimensions, distances, and visited status let maze = new Array(MAXN).fill( null ).map(() => new Array(MAXN)); let n, m; let distanceFromStart = new Array(MAXN * MAXN).fill(INF); let distanceFromRat1 = new Array(MAXN * MAXN).fill(INF); let distanceFromRat2 = new Array(MAXN * MAXN).fill(INF); let visited = new Array(MAXN).fill( null ).map(() => new Array(MAXN).fill( false )); // List to store unlocked cells and queue for BFS operations let unlockedCells = []; let Q = []; // Movement steps: Down, Right, Up, Left const step = [ [1, 0], [0, 1], [-1, 0], [0, -1] ]; // Depth-first search function to explore the maze and mark distances function dfs(x, y, d, distance) { for (let i = 0; i < 4; i++) { let u = x + step[i][0]; let v = y + step[i][1]; // Check if the new coordinates are within bounds if (u >= 0 && v >= 0 && u < n && v < m) { // Skip visited cells, obstacles, and out-of-bounds cells if (visited[u][v] || maze[u][v] === '*' || maze[u][v] === '$' ) continue ; distance[m * u + v] = d; visited[u][v] = true ; // If the cell is a door, increment the distance and add to the queue if (maze[u][v] === '#' ) { distance[m * u + v]++; Q.push(m * u + v); } else { dfs(u, v, d, distance); } } } } // Breadth-first search function to traverse the maze and compute distances function bfs(distance) { while (Q.length) { let p = Q.shift(); let x = Math.floor(p / m), y = p % m; dfs(x, y, distance[m * x + y], distance); // Perform DFS from the current cell } } // Main function to start the operations function main() { let T = 1; // Number of test cases while (T-- > 0) { n = 5; // Number of rows in the maze m = 9; // Number of columns in the maze // Input maze structure let inputMaze = [ "****#****" , "*..#.#..*" , "****.****" , "*$#.#.#$*" , "*********" ].map(row => row.split( '' )); // Copy input maze to the actual maze for (let i = 0; i < n; i++) { maze[i] = [...inputMaze[i]]; } for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if ((i === 0 || j === 0 || i === n - 1 || j === m - 1) && (maze[i][j] === '.' || maze[i][j] === '$' )) { Q.push(m * i + j); distanceFromStart[m * i + j] = 0; visited[i][j] = true ; } } } let rat1Pos = 0, rat2Pos = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (maze[i][j] === '*' ) continue ; if ((i === 0 || j === 0 || i === n - 1 || j === m - 1) && maze[i][j] === '#' ) { distanceFromStart[m * i + j] = 1; Q.push(m * i + j); visited[i][j] = true ; } if (maze[i][j] === '#' ) unlockedCells.push(m * i + j); if (maze[i][j] === '$' ) { if (!rat1Pos) { rat1Pos = m * i + j; distanceFromRat1[rat1Pos] = 0; } else { rat2Pos = m * i + j; distanceFromRat2[rat2Pos] = 0; } } } } bfs(distanceFromStart); for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { visited[i][j] = false ; } } visited[Math.floor(rat1Pos / m)][rat1Pos % m] = true ; Q.push(rat1Pos); bfs(distanceFromRat1); for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { visited[i][j] = false ; } } visited[Math.floor(rat2Pos / m)][rat2Pos % m] = true ; Q.push(rat2Pos); bfs(distanceFromRat2); let ans = distanceFromStart[rat1Pos] + distanceFromStart[rat2Pos]; for (let i = 0; i < unlockedCells.length; i++) { ans = Math.min( ans, distanceFromRat1[unlockedCells[i]] + distanceFromRat2[unlockedCells[i]] + distanceFromStart[unlockedCells[i]] - 2 ); } console.log(ans); } } main(); // This code is contributed by akshitaguprzj3 |
4
Time complexity: O(N * M), where N is the number of rows and M is the number of columns in the maze. The primary factor contributing to this complexity is the breadth-first search (BFS) operation, which explores the maze cells.
Auxiliary Space : O(N * M), where N is the number of rows and M is the number of columns in the maze.
Contact Us