You are given two positive integers xCorner and yCorner, and a 2D array circles, where…
- User
You are given two positive integers xCorner and yCorner, and a 2D array circles, where circles[i] = [xi, yi, ri] denotes a circle with center at (xi, yi) and radius ri. There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate (xCorner, yCorner). You need to check whether there is a path from the bottom left corner to the top right corner such that the entire path lies inside the rectangle, does not touch or lie inside any circle, and touches the rectangle only at the two corners. Return true if such a path exists, and false otherwise.
Example 1: Input: xCorner = 3, yCorner = 4, circles = [[2,1,1]] Output: true
Example 2: Input: xCorner = 3, yCorner = 3, circles = [[1,1,2]] Output: false
Example 3: Input: xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]] Output: false
Example 4: Input: xCorner = 4, yCorner = 4, circles = [[5,5,1]] Output: true
Constraints: 3 <= xCorner, yCorner <= 10^9 1 <= circles.length <= 1000 circles[i].length == 3 1 <= xi, yi, ri <= 10^9
Write code in C++ as one function.
- Assistant
To solve the problem of checking whether there exists a valid path from the bottom-left corner
(0, 0)to the top-right corner(xCorner, yCorner)of a rectangle without touching any of the given circles, we can leverage the Union-Find (Disjoint Set Union) data structure.Key Insights:
-
Blocked Path Condition:
- A path is blocked if there exists a connected component of circles that forms a barrier either from left to right or from top to bottom of the rectangle.
- Specifically, if a set of circles touches both the left and right boundaries, or both the top and bottom boundaries, then no valid path exists.
-
Union-Find Application:
- Treat each circle as a node.
- Additionally, represent the four boundaries (
left,right,top,bottom) as separate nodes. - Union two circles if they intersect or touch each other.
- Union a circle with a boundary if it touches that boundary.
- After forming all unions, check if the
leftboundary is connected to therightboundary or if thetopboundary is connected to thebottomboundary. If either condition is true, returnfalseindicating no valid path exists. Otherwise, returntrue.
Implementation Steps:
-
Initialize Union-Find Structure:
- Each circle is given a unique index from
0ton-1. - Assign additional indices to represent the boundaries:
left = n,right = n+1,bottom = n+2,top = n+3.
- Each circle is given a unique index from
-
Union Circles with Boundaries:
- For each circle, check if it touches any of the four boundaries and perform the union operation accordingly.
-
Union Intersecting Circles:
- For every pair of circles, check if they intersect or touch by comparing the squared distance between their centers with the squared sum of their radii. If they do, perform a union operation.
-
Check for Blockage:
- After all unions, check if the
leftboundary is connected to therightboundary or if thetopboundary is connected to thebottomboundary.
- After all unions, check if the
-
Return Result:
- If either boundary pair is connected, return
false. Otherwise, returntrue.
- If either boundary pair is connected, return
Final Implementation:
#include <vector> #include <cmath> using namespace std; typedef long long ll; class UnionFind { public: vector<int> parent; UnionFind(int size){ parent.resize(size); for(int i=0;i<size;i++) parent[i] = i; } int find_set(int x){ if(parent[x]!=x){ parent[x] = find_set(parent[x]); } return parent[x]; } void union_set(int x, int y){ int fx = find_set(x); int fy = find_set(y); if(fx != fy){ parent[fx] = fy; } } }; bool isPathAvailable(int xCorner, int yCorner, vector<vector<int>>& circles) { int n = circles.size(); // Define indices for boundaries // 0 to n-1: circles // n: left, n+1: right, n+2: bottom, n+3: top int left = n, right = n+1, bottom = n+2, top = n+3; UnionFind uf(n + 4); // Union circles with boundaries if they touch for(int i=0;i<n;i++){ ll xi = circles[i][0]; ll yi = circles[i][1]; ll ri = circles[i][2]; if(xi - ri <= 0){ uf.union_set(i, left); } if(xi + ri >= xCorner){ uf.union_set(i, right); } if(yi - ri <= 0){ uf.union_set(i, bottom); } if(yi + ri >= yCorner){ uf.union_set(i, top); } } // Union circles that intersect or touch for(int i=0;i<n;i++){ ll xi = circles[i][0]; ll yi = circles[i][1]; ll ri = circles[i][2]; for(int j=i+1;j<n;j++){ ll xj = circles[j][0]; ll yj = circles[j][1]; ll rj = circles[j][2]; ll dx = xi - xj; ll dy = yi - yj; ll dist_sq = dx*dx + dy*dy; ll rad_sum = ri + rj; if(dist_sq <= (ll)rad_sum * rad_sum){ uf.union_set(i, j); } } } // Check if left and right are connected or top and bottom are connected if(uf.find_set(left) == uf.find_set(right) || uf.find_set(top) == uf.find_set(bottom)){ return false; } return true; }Explanation of Examples:
-
Example 1:
- Input:
xCorner = 3,yCorner = 4,circles = [[2,1,1]] - Output:
true - Reason: The single circle does not block the path from
(0,0)to(3,4).
- Input:
-
Example 2:
- Input:
xCorner = 3,yCorner = 3,circles = [[1,1,2]] - Output:
false - Reason: The circle covers the entire rectangle, blocking any path.
- Input:
-
Example 3:
- Input:
xCorner = 3,yCorner = 3,circles = [[2,1,1],[1,2,1]] - Output:
false - Reason: The two circles together block the path by connecting both left-right and top-bottom boundaries.
- Input:
-
Example 4:
- Input:
xCorner = 4,yCorner = 4,circles = [[5,5,1]] - Output:
true - Reason: The circle is outside the rectangle and does not interfere with the path.
- Input:
-