Given a 2D matrix grid of size n x n, where each cell contains either a robber (denoted by 1), is empty (denoted by 0), or an obstacle (denoted by -1). Your starting position is at cell (0, 0), and you can move to any adjacent cell in the grid, including cells containing robbers but you cannot move to any cell having obstacles. The safety factor of a path on the grid is defined as the minimum Manhattan distance from any cell in the path to any robber in the grid. Your task is to find the maximum safety factor among all paths leading to cell (n – 1, n – 1) while avoiding the obstacles in the path.
Examples:
Input: grid[][] = [[0, 0, 1], [0, -1, 0], [0, 0, 0]]
Output: 2
Explanation: The path depicted has a safety factor of 2 since: The closest cell of the path to the thief at cell (0, 2) is cell (0, 0) and the obstacle is at (1, 1) which does not matter in this case. The distance between them is | 0 – 0 | + | 0 – 2 | = 2.
Input: grid[][] = [[0, 0, -1, 0], [0, 0, 0, -1], [0, -1, 0, 0], [1, 0, 0, 0]]
Output: 3
Explanation: The path depicted in the picture has a safety factor of 3 .The closest cell of the path to the robber at cell (3, 0) is cell (0, 0). The distance between them is |0 – 3| + |0 – 0| = 3. The closest cell of the path to the robber at cell (3, 0) is cell (3, 2). The distance between them is |3 – 3| + |0 – 2| = 2. The maximum safety factor among all paths leading to cell (3, 3) is 3.
Approach: To solve the problem follow the below Idea:
At first, on reading the question, the first intuition that hits our mind is to use the Breadth-First search (BFS) algorithm as we have to explore nearby cells step by step. After this step, we have to optimally find the maximum safety factor which can be obtained by using a smart search technique like Binary Search using the BFS matrix. Important thing to consider here is the obstacles which we do not have to take into consideration.
Follow the steps to solve the problem:
- Create a 2D matrix ‘dist’ to hold the shortest path to each cell from any cell containing a thief. Calculate the distance of the nearest cell containing a thief (‘1’). Article for reference: https://www.neveropen.co.uk/distance-nearest-cell-1-binary-matrix/
- Create a queue of 3 items – {x-coordinate, y-coordinate, steps}.
- For each cell, mark it as visited and push it into the queue with the step count as 0.
- Perform BFS accordingly and determine the distance. Update the dist matrix accordingly.
- Keep a check if there occurs any obstacles in the grid. If none occurs, then only continue the BFS traversal from that cell.
- Once the required distance is found, use the binary search to find the maximum safety factor.
- Initialize the ‘low’ and ‘high’ pointers. Perform binary search and find the mid value.
- Now again traverse through the dist matrix by performing another BFS function to check if a path with a safety factor of mid is feasible.
- If feasible, update the ‘ans’ variable and update low = mid + 1. If not feasible, update high = mid – 1.
- For the second BFS function, start from the top-left cell. Explore the adjacent cells and check if they satisfy the safety factor condition.
- If the bottom-right cell is reached, return true. Otherwise, return false.
Below is the implementation of the above idea:
C++
// C++ code for the above aprpoach:#include <bits/stdc++.h>using namespace std;// Function to perform BFS and check if the// ending point is reachable with given// safety factorbool bfs(vector<vector<int> >& dist, int s){ int n = dist.size(); queue<pair<int, int> > q; vector<vector<int> > vis(n, vector<int>(n, 0)); q.push({ 0, 0 }); vis[0][0] = 1; // Possible moves: up, right, down, left. int delRow[] = { -1, 0, 1, 0 }; int delCol[] = { 0, 1, 0, -1 }; while (!q.empty()) { int r = q.front().first; int c = q.front().second; q.pop(); // Ending point reached if (r == n - 1 && c == n - 1) { return true; } // Traverse in all the four directions for (int i = 0; i < 4; i++) { int nrow = r + delRow[i]; int ncol = c + delCol[i]; // Check if the next cell is within // the given constraints and // appropriate conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < n && dist[nrow][ncol] >= s && !vis[nrow][ncol]) { q.push({ nrow, ncol }); vis[nrow][ncol] = 1; } } } // Ending point not reachable return false;}// Driver functionint main(){ // Grid dimensions int n = 3; int m = 3; vector<vector<int> > grid = { { 0, 0, 1 }, { 0, -1, 0 }, { 0, 0, 0 } }; // Initialize the distance and // the visited arrays vector<vector<int> > vis(n, vector<int>(m, 0)); vector<vector<int> > dist(n, vector<int>(m, 0)); queue<pair<pair<int, int>, int> > q; // Initialize the queue for BFS for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { vis[i][j] = 1; q.push({ { i, j }, 0 }); } } } // Possible moves: up, right, down, left. int delRow[] = { -1, 0, 1, 0 }; int delCol[] = { 0, 1, 0, -1 }; // Perform BFS traversal to calculate // distances from the nearest cell // containing a robber, considering obstacles while (!q.empty()) { int row = q.front().first.first; int col = q.front().first.second; int steps = q.front().second; q.pop(); dist[row][col] = steps; for (int i = 0; i < 4; i++) { int nrow = row + delRow[i]; int ncol = col + delCol[i]; // Check all the necessary conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && vis[nrow][ncol] == 0 && grid[nrow][ncol] != -1) { vis[nrow][ncol] = 1; q.push({ { nrow, ncol }, steps + 1 }); } } } // Perform binary search to find the maximum // safeness factor, considering obstacles int low = 0, high = 1e9, ans = 0; while (low <= high) { int mid = (low + high) / 2; if (bfs(dist, mid)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } // Print the maximum safety factor cout << "Maximum Safety Factor: " << ans << endl; return 0;} |
Java
// Java code for the above aprpoach:import java.util.*;// utility pair class with generic typesclass Pair<K, E> { K first; E second; Pair(K f, E s) { first = f; second = s; }}class GFG { // Function to perform BFS and check if the // ending point is reachable with given // safety factor static boolean bfs(int[][] dist, int s) { int n = dist.length; Queue<Pair<Integer, Integer> > q = new ArrayDeque<>(); boolean[][] vis = new boolean[n][n]; q.add(new Pair<Integer, Integer>(0, 0)); vis[0][0] = true; // Possible moves: up, right, down, left. int delRow[] = { -1, 0, 1, 0 }; int delCol[] = { 0, 1, 0, -1 }; while (!q.isEmpty()) { int r = q.peek().first; int c = q.peek().second; q.poll(); // Ending point reached if (r == n - 1 && c == n - 1) { return true; } // Traverse in all the four directions for (int i = 0; i < 4; i++) { int nrow = r + delRow[i]; int ncol = c + delCol[i]; // Check if the next cell is within // the given constraints and // appropriate conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < n && dist[nrow][ncol] >= s && !vis[nrow][ncol]) { q.add(new Pair(nrow, ncol)); vis[nrow][ncol] = true; } } } // Ending point not reachable return false; } // Driver function public static void main(String[] args) { // Grid dimensions int n = 3; int m = 3; int[][] grid = { { 0, 0, 1 }, { 0, -1, 0 }, { 0, 0, 0 } }; // Initialize the distance and // the visited arrays boolean[][] vis = new boolean[n][m]; int[][] dist = new int[n][m]; Queue<Pair<Pair<Integer, Integer>, Integer> > q = new ArrayDeque<>(); // Initialize the queue for BFS for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { vis[i][j] = true; q.add(new Pair<Pair<Integer, Integer>, Integer>( new Pair<Integer, Integer>(i, j), 0)); } } } // Possible moves: up, right, down, left. int delRow[] = { -1, 0, 1, 0 }; int delCol[] = { 0, 1, 0, -1 }; // Perform BFS traversal to calculate // distances from the nearest cell // containing a robber, considering obstacles while (!q.isEmpty()) { int row = q.peek().first.first; int col = q.peek().first.second; int steps = q.peek().second; q.poll(); dist[row][col] = steps; for (int i = 0; i < 4; i++) { int nrow = row + delRow[i]; int ncol = col + delCol[i]; // Check all the necessary conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && !vis[nrow][ncol] && grid[nrow][ncol] != -1) { vis[nrow][ncol] = true; q.add(new Pair<Pair<Integer, Integer>, Integer>( new Pair<Integer, Integer>(nrow, ncol), steps + 1)); } } } // Perform binary search to find the maximum // safeness factor, considering obstacles int low = 0, high = (int)1e9, ans = 0; while (low <= high) { int mid = (low + high) / 2; if (bfs(dist, mid)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } // Print the maximum safety factor System.out.println("Maximum Safety Factor: " + ans); }}// This code is contributed by ragul21 |
Python3
# Python code for the above approachfrom queue import Queue# Function to perform BFS and check if the# ending point is reachable with given# safety factordef bfs(dist, s): n = len(dist) q = Queue() vis = [[0 for _ in range(n)] for _ in range(n)] q.put((0, 0)) vis[0][0] = 1 # Possible moves: up, right, down, left. delRow = [-1, 0, 1, 0] delCol = [0, 1, 0, -1] while not q.empty(): r, c = q.get() # Ending point reached if r == n - 1 and c == n - 1: return True # Traverse in all four directions for i in range(4): nrow = r + delRow[i] ncol = c + delCol[i] # Check if the next cell is within # the given constraints and # appropriate conditions if 0 <= nrow < n and 0 <= ncol < n and dist[nrow][ncol] >= s and not vis[nrow][ncol]: q.put((nrow, ncol)) vis[nrow][ncol] = 1 # Ending point not reachable return False# Driver functiondef main(): # Grid dimensions n = 3 m = 3 grid = [[0, 0, 1], [0, -1, 0], [0, 0, 0]] # Initialize the distance and # the visited arrays vis = [[0 for _ in range(m)] for _ in range(n)] dist = [[0 for _ in range(m)] for _ in range(n)] q = Queue() # Initialize the queue for BFS for i in range(n): for j in range(m): if grid[i][j] == 1: vis[i][j] = 1 q.put(((i, j), 0)) # Possible moves: up, right, down, left. delRow = [-1, 0, 1, 0] delCol = [0, 1, 0, -1] # Perform BFS traversal to calculate # distances from the nearest cell # containing a robber, considering obstacles while not q.empty(): (row, col), steps = q.get() dist[row][col] = steps for i in range(4): nrow = row + delRow[i] ncol = col + delCol[i] # Check all the necessary conditions if 0 <= nrow < n and 0 <= ncol < m and vis[nrow][ncol] == 0 and grid[nrow][ncol] != -1: vis[nrow][ncol] = 1 q.put(((nrow, ncol), steps + 1)) # Perform binary search to find the maximum # safeness factor, considering obstacles low, high, ans = 0, 1e9, 0 while low <= high: mid = (low + high) // 2 if bfs(dist, mid): ans = mid low = mid + 1 else: high = mid - 1 # Print the maximum safety factor print("Maximum Safety Factor:", ans)if __name__ == "__main__": main()# This code is contributed by ragul21 |
C#
// C# code for the above aprpoachusing System;using System.Collections.Generic;class GFG { // Function to perform BFS and check if the // ending point is reachable with given // safety factor static bool BFS(List<List<int>> dist, int s) { int n = dist.Count; Queue<Tuple<int, int>> q = new Queue<Tuple<int, int>>(); List<List<int>> vis = new List<List<int>>(); for (int i = 0; i < n; i++) { vis.Add(new List<int>()); for (int j = 0; j < n; j++) { vis[i].Add(0); } } q.Enqueue(new Tuple<int, int>(0, 0)); vis[0][0] = 1; // Possible moves: up, right, down, left. int[] delRow = { -1, 0, 1, 0 }; int[] delCol = { 0, 1, 0, -1 }; while (q.Count != 0) { Tuple<int, int> current = q.Dequeue(); int r = current.Item1; int c = current.Item2; // Ending point reached if (r == n - 1 && c == n - 1) { return true; } // Traverse in all the four directions for (int i = 0; i < 4; i++) { int nrow = r + delRow[i]; int ncol = c + delCol[i]; // Check if the next cell is within // the given constraints and // appropriate conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < n && dist[nrow][ncol] >= s && vis[nrow][ncol] == 0) { q.Enqueue(new Tuple<int, int>(nrow, ncol)); vis[nrow][ncol] = 1; } } } // Ending point not reachable return false; } // Driver function static void Main(string[] args) { // Grid dimensions int n = 3; int m = 3; List<List<int>> grid = new List<List<int>> { new List<int> { 0, 0, 1 }, new List<int> { 0, -1, 0 }, new List<int> { 0, 0, 0 } }; // Initialize the distance and // the visited arrays List<List<int>> vis = new List<List<int>>(); List<List<int>> dist = new List<List<int>>(); Queue<Tuple<Tuple<int, int>, int>> q = new Queue<Tuple<Tuple<int, int>, int>>(); for (int i = 0; i < n; i++) { vis.Add(new List<int>()); dist.Add(new List<int>()); for (int j = 0; j < m; j++) { vis[i].Add(0); dist[i].Add(0); if (grid[i][j] == 1) { vis[i][j] = 1; q.Enqueue(new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(i, j), 0)); } } } // Possible moves: up, right, down, left. int[] delRow = { -1, 0, 1, 0 }; int[] delCol = { 0, 1, 0, -1 }; // Perform BFS traversal to calculate // distances from the nearest cell // containing a robber, considering obstacles while (q.Count != 0) { Tuple<Tuple<int, int>, int> current = q.Dequeue(); int row = current.Item1.Item1; int col = current.Item1.Item2; int steps = current.Item2; dist[row][col] = steps; for (int i = 0; i < 4; i++) { int nrow = row + delRow[i]; int ncol = col + delCol[i]; // Check all the necessary conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && vis[nrow][ncol] == 0 && grid[nrow][ncol] != -1) { vis[nrow][ncol] = 1; q.Enqueue(new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(nrow, ncol), steps + 1)); } } } // Perform binary search to find the maximum // safeness factor, considering obstacles int low = 0, high = 1000000000, ans = 0; while (low <= high) { int mid = (low + high) / 2; if (BFS(dist, mid)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } // Print the maximum safety factor Console.WriteLine("Maximum Safety Factor: " + ans); }} |
Javascript
// Function to perform BFS and check if the ending point is reachable with the given safety factorfunction bfs(dist, s) { const n = dist.length; const vis = new Array(n).fill(null).map(() => new Array(n).fill(false)); const queue = []; queue.push([0, 0]); vis[0][0] = true; // Possible moves: up, right, down, left. const delRow = [-1, 0, 1, 0]; const delCol = [0, 1, 0, -1]; while (queue.length !== 0) { const [r, c] = queue.shift(); // Ending point reached if (r === n - 1 && c === n - 1) { return true; } // Traverse in all four directions for (let i = 0; i < 4; i++) { const nrow = r + delRow[i]; const ncol = c + delCol[i]; // Check if the next cell is within the given constraints and appropriate conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < n && dist[nrow][ncol] >= s && !vis[nrow][ncol]) { queue.push([nrow, ncol]); vis[nrow][ncol] = true; } } } // Ending point not reachable return false;}// Driver functionfunction main() { // Grid dimensions const n = 3; const m = 3; const grid = [ [0, 0, 1], [0, -1, 0], [0, 0, 0] ]; // Initialize the distance and the visited arrays const vis = new Array(n).fill(null).map(() => new Array(m).fill(false)); const dist = new Array(n).fill(null).map(() => new Array(m).fill(0)); const queue = []; // Initialize the queue for BFS for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (grid[i][j] === 1) { vis[i][j] = true; queue.push([i, j, 0]); } } } // Possible moves: up, right, down, left. const delRow = [-1, 0, 1, 0]; const delCol = [0, 1, 0, -1]; // Perform BFS traversal to calculate distances from the nearest cell containing a robber, considering obstacles while (queue.length !== 0) { const [row, col, steps] = queue.shift(); dist[row][col] = steps; for (let i = 0; i < 4; i++) { const nrow = row + delRow[i]; const ncol = col + delCol[i]; // Check all the necessary conditions if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && !vis[nrow][ncol] && grid[nrow][ncol] !== -1) { vis[nrow][ncol] = true; queue.push([nrow, ncol, steps + 1]); } } } // Perform binary search to find the maximum safeness factor, considering obstacles let low = 0, high = 1e9, ans = 0; while (low <= high) { const mid = Math.floor((low + high) / 2); if (bfs(dist, mid)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } // Print the maximum safety factor console.log(`Maximum Safety Factor: ${ans}`);}// Calling the main functionmain(); |
Output
Maximum Safety Factor: 2
Time Complexity: O(N2), Since each cell of the 2D matrix is visited once during the BFS traversal, the worst case scenario takes O(N2) time.
Auxiliary Space: O(N2), Due to the dist matrix, vis matrix, and the BFS queue, the overall space complexity of the algorithm is O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
