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.
We need to find a path from (0,0) to (xCorner, yCorner) inside the rectangle, avoiding all circles. The problem reduces to a grid-based pathfinding problem with forbidden cells (those inside or on any circle). BFS or DFS can be used to explore the grid.
By marking all points that are inside or on any circle as blocked, we can use BFS or DFS to check if there is a path from the bottom-left to the top-right corner. Since the rectangle is small (max 100x100), this approach is efficient.
classSolution {
public:bool isReachable(int xCorner, int yCorner, vector<vector<int>>& circles) {
int n = xCorner, m = yCorner;
vector<vector<bool>> blocked(n+1, vector<bool>(m+1, false));
for (auto& c : circles) {
int cx = c[0], cy = c[1], r = c[2];
for (int x =0; x <= n; ++x) {
for (int y =0; y <= m; ++y) {
int dx = x - cx, dy = y - cy;
if (dx*dx + dy*dy <= r*r) blocked[x][y] = true;
}
}
}
if (blocked[0][0] || blocked[n][m]) return false;
queue<pair<int,int>> q;
q.push({0,0});
blocked[0][0] = true;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == n && y == m) return true;
for (auto& d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >=0&& nx <= n && ny >=0&& ny <= m &&!blocked[nx][ny]) {
blocked[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
};
classSolution {
publicbooleanisReachable(int xCorner, int yCorner, int[][] circles) {
int n = xCorner, m = yCorner;
boolean[][] blocked =newboolean[n+1][m+1];
for (int[] c : circles) {
int cx = c[0], cy = c[1], r = c[2];
for (int x = 0; x <= n; x++) {
for (int y = 0; y <= m; y++) {
int dx = x - cx, dy = y - cy;
if (dx*dx + dy*dy <= r*r) blocked[x][y]=true;
}
}
}
if (blocked[0][0]|| blocked[n][m]) returnfalse;
Queue<int[]> q =new LinkedList<>();
q.add(newint[]{0,0});
blocked[0][0]=true;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
if (x == n && y == m) returntrue;
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m &&!blocked[nx][ny]) {
blocked[nx][ny]=true;
q.add(newint[]{nx, ny});
}
}
}
returnfalse;
}
}
classSolution {
funisReachable(xCorner: Int, yCorner: Int, circles: Array<IntArray>): Boolean {
val n = xCorner; val m = yCorner
val blocked = Array(n+1) { BooleanArray(m+1) }
for (c in circles) {
val cx = c[0]; val cy = c[1]; val r = c[2]
for (x in0..n) for (y in0..m) {
val dx = x - cx; val dy = y - cy
if (dx*dx + dy*dy <= r*r) blocked[x][y] = true }
}
if (blocked[0][0] || blocked[n][m]) returnfalseval dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
val q = ArrayDeque<Pair<Int,Int>>()
q.add(0 to 0)
blocked[0][0] = truewhile (q.isNotEmpty()) {
val(x, y) = q.removeFirst()
if (x == n && y == m) returntruefor (d in dirs) {
val nx = x + d[0]; val ny = y + d[1]
if (nx in0..n && ny in0..m && !blocked[nx][ny]) {
blocked[nx][ny] = true q.add(nx to ny)
}
}
}
returnfalse }
}
classSolution:
defis_reachable(self, xCorner: int, yCorner: int, circles: list[list[int]]) -> bool:
n, m = xCorner, yCorner
blocked = [[False]*(m+1) for _ in range(n+1)]
for cx, cy, r in circles:
for x in range(n+1):
for y in range(m+1):
if (x-cx)**2+ (y-cy)**2<= r*r:
blocked[x][y] =Trueif blocked[0][0] or blocked[n][m]:
returnFalsefrom collections import deque
q = deque([(0,0)])
blocked[0][0] =True dirs = [(1,0),(-1,0),(0,1),(0,-1)]
while q:
x, y = q.popleft()
if x == n and y == m:
returnTruefor dx, dy in dirs:
nx, ny = x+dx, y+dy
if0<= nx <= n and0<= ny <= m andnot blocked[nx][ny]:
blocked[nx][ny] =True q.append((nx, ny))
returnFalse
impl Solution {
pubfnis_reachable(x_corner: i32, y_corner: i32, circles: Vec<Vec<i32>>) -> bool {
let n = x_corner asusize;
let m = y_corner asusize;
letmut blocked =vec![vec![false; m+1]; n+1];
for c in&circles {
let (cx, cy, r) = (c[0], c[1], c[2]);
for x in0..=n {
for y in0..=m {
let dx = x asi32- cx;
let dy = y asi32- cy;
if dx*dx + dy*dy <= r*r {
blocked[x][y] =true;
}
}
}
}
if blocked[0][0] || blocked[n][m] {
returnfalse;
}
let dirs = [(1,0),(-1,0),(0,1),(0,-1)];
letmut q = std::collections::VecDeque::new();
q.push_back((0,0));
blocked[0][0] =true;
whilelet Some((x, y)) = q.pop_front() {
if x == n && y == m {
returntrue;
}
for (dx, dy) in dirs.iter() {
let nx = x asi32+ dx;
let ny = y asi32+ dy;
if nx >=0&& nx <= n asi32&& ny >=0&& ny <= m asi32&&!blocked[nx asusize][ny asusize] {
blocked[nx asusize][ny asusize] =true;
q.push_back((nx asusize, ny asusize));
}
}
}
false }
}
⏰ Time complexity: O((n*m)*k), where n and m are the rectangle dimensions and k is the number of circles, as we check each cell for each circle and perform BFS/DFS.
🧺 Space complexity: O(n*m), as we store the blocked grid and BFS/DFS queue.