We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Determine if a Cell Is Reachable at a Given Time

Difficulty: Medium

Problem Description

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.

Key Insights

  • The distance between the starting cell and the target cell can be calculated using the Chebyshev distance, which is max(abs(fx - sx), abs(fy - sy)).
  • To reach the target cell in exactly t seconds, the distance must be less than or equal to t, and the difference between t and the distance must be even (to allow for returning to the same cell if necessary).
  • If the distance to the target is greater than t, it's impossible to reach the target in the given time.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The solution involves calculating the Chebyshev distance between the starting cell and the target cell, and checking if it is possible to reach the target cell in the specified time. This can be done using simple arithmetic operations to determine the distance and its relation to t.

Code Solutions

def canReachCell(sx, sy, fx, fy, t):
    # Calculate the Chebyshev distance
    distance = max(abs(fx - sx), abs(fy - sy))
    # Check if we can reach (fx, fy) in exactly t seconds
    return distance <= t and (t - distance) % 2 == 0
← Back to All Questions