Consider a grid of dimensions NxM and an array R consisting of available circular obstacles, the task is to find the minimum number of circular obstacles of given radiuses required to obstruct the path between source [0, 0] and destination [N-1, M-1]. If not possible, print -1.
Note: The circular obstacles can overlap as shown in the image in example 1.
Examples:
Input: N = 4, M = 5, R[] = {1.0, 1.5, 1.25}
Output: 2
Input: N = 10, M = 12, R[] = {1.0, 1.25}
Output: -1
Approach:
- Find whether to put the obstacles row-wise or column-wise.
- Sort the radius in decreasing order.
- Since the obstacles cover an entire circle with radius R[i], therefore, for a straight line, it covers the diameter.
- Decrease the val by 2 * Ri until it becomes zero using larger values in array R[].
- After using all the obstacles, when val <= 0 return the count of obstacles used, and if the val > 0 after using all the obstacles, print -1.
Below is the implementation of the above approach.
CPP
// C++ program to find the minimum// number of obstacles required#include <bits/stdc++.h>using namespace std;// Function to find the minimum// number of obstacles requiredint solve(int n, int m, int obstacles, double range[]){ // Find the minimum range required // to put obstacles double val = min(n, m); // Sorting the radius sort(range, range + obstacles); int c = 1; for (int i = obstacles - 1; i >= 0; i--) { range[i] = 2 * range[i]; val -= range[i]; // If val is less than zero // then we have find the number of // obstacles required if (val <= 0) { return c; } else { c++; } } if (val > 0) { return -1; }}// Driver functionint main(){ int n = 4, m = 5, obstacles = 3; double range[] = { 1.0, 1.25, 1.15 }; cout << solve(n, m, obstacles, range) << "\n"; return 0;} |
Java
// Java program to find the minimum// number of obstacles requiredimport java.util.*;class GFG{// Function to find the minimum// number of obstacles requiredstatic int solve(int n, int m, int obstacles, double range[]){ // Find the minimum range required // to put obstacles double val = Math.min(n, m); // Sorting the radius Arrays.sort(range); int c = 1; for (int i = obstacles - 1; i >= 0; i--) { range[i] = 2 * range[i]; val -= range[i]; // If val is less than zero // then we have find the number of // obstacles required if (val <= 0) { return c; } else { c++; } } if (val > 0) { return -1; } return 0;}// Driver codepublic static void main(String[] args){ int n = 4, m = 5, obstacles = 3; double range[] = { 1.0, 1.25, 1.15 }; System.out.print(solve(n, m, obstacles, range)+ "\n");}}// This code is contributed by PrinciRaj1992 |
C#
// C# program to find the minimum// number of obstacles requiredusing System;class GFG{ // Function to find the minimum // number of obstacles required static int solve(int n, int m, int obstacles, double []range) { // Find the minimum range required // to put obstacles double val = Math.Min(n, m); // Sorting the radius Array.Sort(range); int c = 1; for (int i = obstacles - 1; i >= 0; i--) { range[i] = 2 * range[i]; val -= range[i]; // If val is less than zero // then we have find the number of // obstacles required if (val <= 0) { return c; } else { c++; } } if (val > 0) { return -1; } return 0; } // Driver code public static void Main() { int n = 4, m = 5, obstacles = 3; double []range = { 1.0, 1.25, 1.15 }; Console.WriteLine(solve(n, m, obstacles, range)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 program to find the minimum# number of obstacles required# Function to find the minimum# number of obstacles requireddef solve(n, m, obstacles,range): # Find the minimum range required # to put obstacles val = min(n, m) # Sorting the radius range = sorted(range) c = 1 for i in range(obstacles - 1, -1, -1): range[i] = 2 * range[i] val -= range[i] # If val is less than zero # then we have find the number of # obstacles required if (val <= 0): return c else: c += 1 if (val > 0): return -1# Driver coden = 4m = 5obstacles = 3range = [1.0, 1.25, 1.15]print(solve(n, m, obstacles, range))# This code is contributed by mohit kumar 29 |
Javascript
<script> // Javascript program to find the minimum// number of obstacles required// Function to find the minimum// number of obstacles requiredfunction solve(n, m, obstacles, range){ // Find the minimum range required // to put obstacles var val = Math.min(n, m); // Sorting the radius range.sort((a,b)=>a-b) var c = 1; for (var i = obstacles - 1; i >= 0; i--) { range[i] = 2 * range[i]; val -= range[i]; // If val is less than zero // then we have find the number of // obstacles required if (val <= 0) { return c; } else { c++; } } if (val > 0) { return -1; }}// Driver functionvar n = 4, m = 5, obstacles = 3;var range = [1.0, 1.25, 1.15];document.write( solve(n, m, obstacles, range) + "<br>");</script> |
Output:
2
Time Complexity: O(N * log(N)), where N is the number of given obstacles.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
