Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input Format
2.2.
Output Format
3.
Sample Testcase
3.1.
Input
3.2.
Output
4.
Approach
5.
Algorithm
6.
Code
6.1.
C++ Code
6.2.
Python Code
6.3.
Time Complexity
6.4.
Auxiliary Space: O(n*m)
7.
Frequently Asked Questions
7.1.
Which traversal is used to find the shortest path?
7.2.
What is the time complexity of BFS?
7.3.
Which is faster in terms of speed: BFS or DFS?
8.
Conclusion
Last Updated: Mar 27, 2024

Find the Path in a Rectangle with Circles

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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.

Find the path in a rectangle with circles

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sample Testcase

Input

m = 5, n = 5, k = 2, r = 1, X = {1, 3}, Y = {3, 3}

Output

Possible

Output graph

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:

Input graph

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.

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don’t worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.  

If you wish to enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, 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. 

Do upvote if you find the blogs helpful.

Happy Learning!

Thank you
Previous article
Find the Number of Nodes between two vertices in an Acyclic Graph using the Disjoint Union Method
Next article
Maximum Number of Edges that can be added to a tree so that it stays a Bipartite graph
Live masterclass