GSSOC'21 Path in a Rectangle with Circles in C++

[kanchan1910]

Hey, I am Kanchan Jeswani, a GSSOC'21 participant I want to add the code for the problem "Path in a Rectangle with Circles ".

The problem statement is as follows :

We have been given a mn rectangular matrix whose top-left(start) location is (1, 1) and bottom-right(end) location is (mn). There are k circles each with radius r. We have to find that if there is any path from start to end without touching any circle.

We can do this by first marking those cells of the rectangle as blocked which comes within any circle and then we can apply BFS on the left unblocked cells to check if the path exists from the starting node to the target node or not.

Sample test cases: Input : m = 5, n = 5, k = 2, r = 1, X = {1, 3}, Y = {3, 3} Output : Possible

here, m and n are the dimensions of the rectangular grid, k is the number of circles, r is the radius of the circles, and two arrays X and Y represent the ( (X[i], Y[i]) ) is the center of the ith circle.

This problem is based on graph theory and basic geometry and is the most important interview problem.

I would love to solve this problem using Python with well-explained code along with its space and time complexity analysis. Please assign me this. Hope to hear from you.

@Rudrakshi ma'am please assign this to me @tarun26091999 please assign this to me, I would love to contribute. Thank you!

[Upasana1216]

I would like to solve this problem using C++. Please assign this to me. @rudrakshi ma'am please assign this to me @tarun26091999 please assign this to me, I would love to contribute. Thank you!