You are given four integers sx, sy, fx, fy, and a non-negative integer t.
In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.
Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.
A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.
Example 1:
Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6 Output: true Explanation: Starting at cell (2, 4), we can reach cell (7, 7) in exactly 6 seconds by going through the cells depicted in the picture above.
Example 2:
Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3 Output: false Explanation: Starting at cell (3, 1), it takes at least 4 seconds to reach cell (7, 3) by going through the cells depicted in the picture above. Hence, we cannot reach cell (7, 3) at the third second.
Constraints:
1 <= sx, sy, fx, fy <= 1090 <= t <= 109This approach leverages the concept of "Manhattan distance" coupled with the "parity check" to determine if the cell can be reached in exactly t steps.
The minimum number of steps required to reach from (sx, sy) to (fx, fy) in a grid is the maximum of the horizontal and vertical distances between these points, known as Chebyshev distance. If this minimal distance is greater than t, the function should return false instantly.
Moreover, if the difference between t and this minimum distance is even, the extra steps required can effectively be taken by oscillating on the grid or taking additional allowable steps. If not, reaching in t steps becomes impossible.
The function calculates the minimum steps needed using the max function for the absolute horizontal and vertical distances. It then checks if these steps are less than or equal to t and if the difference is even to return true or false.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1), as it involves simple arithmetic operations.
Space Complexity: O(1), as no extra space is used.
This approach models the grid and implements a Breadth-First Search (BFS) to simulate traversing from the starting point to check if reaching precisely at t seconds is possible.
Instead of directly computing the distance, this method carries out a brute-force simulation of the movement, exploring all potential paths using a FIFO queue structure inherent to BFS algorithms. The goal is to maintain a count of steps and analyze pathways that may uniquely cover the grid in t steps.
This approach is conceptual as implementing full BFS is impractical for infinite grids or large bounds directly within C without optimized constraints.
The BFS is understood as a simulation iterating every possible step sequence up to t.
C++
Java
Python
C#
JavaScript
Time Complexity: Highly complex, typically O(n^2).
Space Complexity: Also complex, with decisions based on array allocations with a theoretical upper limit.
| Approach | Complexity |
|---|---|
| Approach 1: Minimum Steps with Parity Check | Time Complexity: O(1), as it involves simple arithmetic operations. Space Complexity: O(1), as no extra space is used. |
| Approach 2: Simulation with BFS Algorithm | Time Complexity: Highly complex, typically O(n^2). Space Complexity: Also complex, with decisions based on array allocations with a theoretical upper limit. |
Determine if a Cell Is Reachable at a Given Time | Intuition | Math | Leetcode - 2849 • codestorywithMIK • 2,773 views views
Watch 9 more video solutions →Practice Determine if a Cell Is Reachable at a Given Time with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor