LeetCode 2543: Check if Point Is Reachable
Problem Description
Explanation:
To solve this problem, we can use a recursive approach to explore all possible paths starting from the point (1, 1) and reaching the target point (targetX, targetY). At each step, we try all four possible moves and recursively check if any of them lead to the target point.
-
Algorithmic Idea:
- Start from the point (1, 1) and recursively explore all possible moves.
- At each step, try all four possible moves: (x, y - x), (x - y, y), (2 * x, y), (x, 2 * y).
- Keep track of visited points to avoid revisiting the same point.
- Return true if we reach the target point, false otherwise.
-
Time Complexity: O(4^N) where N is the number of steps required to reach the target point.
-
Space Complexity: O(N) for the recursion stack.
:
Solutions
class Solution {
public boolean isReachable(int targetX, int targetY) {
return canReach(1, 1, targetX, targetY, new HashSet<>());
}
private boolean canReach(int currX, int currY, int targetX, int targetY, Set<String> visited) {
if (currX > targetX || currY > targetY || !visited.add(currX + "-" + currY)) {
return false;
}
if (currX == targetX && currY == targetY) {
return true;
}
return canReach(currX, currX + currY, targetX, targetY, visited) ||
canReach(currX + currY, currY, targetX, targetY, visited) ||
canReach(2 * currX, currY, targetX, targetY, visited) ||
canReach(currX, 2 * currY, targetX, targetY, visited);
}
}Loading editor...