Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
In this article, we will discuss about the Find the path in a rectangle with circles problem, along with a sample test case and approach to solve the problem.
Problem Statement
We are given an M*N rectangular matrix and ‘k’ circles, each with a radius ‘r’. Such that the starting point location of the matrix is (1,1) and the endpoint location is (M, N). The task is to find whether or not there exists any path from the start point to the end point without touching any circle.
Input Format
The input consists of four integer values: m, n, k, r, and two arrays of integers X and Y, each of k length.
m - number of rows in the matrix
n - number of columns in the matrix
k - number of circles
r - radius of each circle
(X[i], Y[i]) - center of the ith circle
Output Format
Print Possible if a path exists from the start point to the endpoint. Otherwise, print Not Possible.
Sample Testcase
Input
m = 5, n = 5, k = 2, r = 1, X = {1, 3}, Y = {3, 3}
Output
Possible
Approach
As mentioned in the problem statement, we need to check if a path exists from the starting point to the end such that we do not use any cell in our path that touches the given circles. To simplify the problem, we need to check for every cell (i,j) of the given rectangle whether it comes within any of the given circles or not. If a cell (i,j) of the rectangle comes within any of the given circles, then mark that cell as ‘blocked’ by assigning it a value of ‘-1’, while marking the rest of the cells as ‘unvisited’ by assigning them with a value’ 0’. To check whether a cell touches any circle, we can simply calculate the distance of the cell from the center of the circle and compare it with the radius ‘r’. If the value is less than ‘r’ it means that the cell lies in the circle, otherwise, it does not.
The given input will look like this:
Now, use the breadth-first search (BFS) to find the shortest path of each cell from the starting point. If the endpoint location (m,n) is marked as visited, then return “Possible”; otherwise, return “Not Possible”.
Algorithm
Take an array named visited of size m*n. Initialize all the cells of the array with a value’ 0’.
Now, for each cell of the rectangle, check whether or not it comes within any of the given circles. If it comes within any given circle, then change the value of visited[i][j] to ‘-1’.
Now apply BFS from the start point, and if a cell (i,j) can be reached, then assign visited[i][j] a value ‘1’.
If the value of the endpoint (visited[m][n]) is 1, then return “Possible”, otherwise, return “Not Possible”.
Code
C++ Code
#include<bits/stdc++.h>
using namespace std;
// function to check whether the newX & newY are valid or not
bool isValid(vector<vector<int> >& visited, int x, int y){
int m = visited.size();
int n = visited[0].size();
if((x>=0) && (y>=0) && (x<m) && (y<n) && visited[x][y]==0)
return true;
else
return false;
}
// a function to check whether a path exists or not
bool isPathPossible(int m, int n, int k, int r, vector<int> X,
vector<int> Y)
{
// visit array to store the status of each cell
vector<vector<int>> visited(m, vector<int>(n,0));
// for every cell, check whether it touches
// any given circle?
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int p = 0; p < k; p++) {
// use the distance formula to compute the distance
int compX=pow((X[p]-1-i),2);
int compY=pow((Y[p]-1-j),2);
if (sqrt(compX + compY) <= r) {
// mark the cell as blocked if it touches the circle
visited[i][j] = -1;
}
}
}
}
// Base Case
// check the start point, if it is blocked
// no path can be formed
if (visited[0][0] == -1)
return false;
// BFS traversal
// a queue to store cells that aren't
// yet discovered
queue<pair<int,int> > q;
int dirX[]={0, 1, -1, 0, 1, -1, -1, 1};
int dirY[]={1, 0, 0, -1, 1, -1, 1, -1};
// mark the start point as visited & push it in the queue
visited[0][0] = 1;
q.push({ 0, 0 });
// Discover cells until the queue is not empty
while (!q.empty()) {
pair<int, int> a = q.front();
q.pop();
int curX = a.first;
int curY = a.second;
for(int i=0;i<8;i++){
int newX = curX + dirX[i];
int newY = curY + dirY[i];
if(isValid(visited, newX, newY)){
visited[newX][newY] = 1;
q.push({newX, newY});
}
}
}
// check if the endpoint is reachable from the start
return (visited[m - 1][n - 1] == 1);
}
int main()
{
int m = 5, n = 5, k = 2, r = 1;
vector<int> X = { 1, 3 };
vector<int> Y = { 3, 3 };
if (isPathPossible(m, n, k, r, X, Y))
cout << "Possible" << endl;
else
cout << "Not Possible" << endl;
return 0;
}
Output:
Possible
Python Code
import math
import queue
# A function to check whether a path exists or not
def checkIfPossible(m, n, k, r, X, Y):
# visit the array to store the status of each cell
visited = [[0] * n for cell in range(m)]
#for every cell, check whether it touches any given circle?
for i in range(m):
for j in range(n):
for p in range(k):
# use the distance formula to compute the distance
compX = pow((X[p] - 1 - i),2)
compY = pow((Y[p] - 1 - j),2)
if (math.sqrt(compX + compY) <= r):
# mark the cell as blocked, if it touches the circle
visited[i][j] = -1
#Base Case
#check the start point, if it is blocked, no path can be formed
if (visited[0][0] == -1):
return False
# BFS traversal
# a queue to store cells that aren't yet discovered
q = queue.Queue()
moves = 8
dirX=[0, 1, -1, 0, 1, -1, -1, 1];
dirY=[1, 0, 0, -1, 1, -1, 1, -1];
# mark the start point as visited & push it in the queue
visited[0][0] = 1
q.put([0, 0])
# Discover cells until the queue is not empty
while (not q.empty()):
a = q.get()
curX = a[0]
curY = a[1]
# check for all adjacent cells
for i in range(moves):
newX = curX + dirX[i]
newY = curY + dirY[i]
if((newX>=0) and (newY>=0) and (newX<m) and (newY<n) and visited[newX][newY]==0):
visited[newX][newY] = 1
q.put([newX, newY])
# check if the endpoint is reachable from the start
return (visited[m - 1][n - 1] == 1)
# Driver Code
if __name__ == '__main__':
m = 5
n = 5
k = 2
r = 1
X = [1, 3]
Y = [3, 3]
# Function call
if (checkIfPossible(m, n, k, r, X, Y)):
print("Possible")
else:
print("Not Possible")
Output:
Possible
Time Complexity
To check for every cell, whether it is within or not in any of the given circles, takes O(m*n*k) time. BFS of the entire rectangle takes O(V+E) time. Therefore, the overall time complexity is O(m*n*k).
Auxiliary Space: O(n*m)
Frequently Asked Questions
Which traversal is used to find the shortest path?
The BFS is used to find the shortest path.
What is the time complexity of BFS?
The time complexity of BFS is O(V+E).
Which is faster in terms of speed: BFS or DFS?
DFS is faster in terms of speed than BFS.
Conclusion
In this article, we have extensively discussed the problem: Finding a path in a rectangle with circles.
If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company.