# Determine if a Cell Is Reachable at a Given Time
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/determine-if-a-cell-is-reachable-at-a-given-time)
Canonical: https://scaleengineer.com/dsa/problems/determine-if-a-cell-is-reachable-at-a-given-time
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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:**

![](https://assets.glich.co/dsa/determine-if-a-cell-is-reachable-at-a-given-time/image0.svg) 

**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:**

![](https://assets.glich.co/dsa/determine-if-a-cell-is-reachable-at-a-given-time/image1.svg) 

**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 <= 109`
* `0 <= t <= 109`

# Approaches
## Brute-force Simulation (BFS)
This approach simulates the process of moving on the grid step by step. We can use a Breadth-First Search (BFS) to explore all possible cells reachable at each second, from 1 to `t`. We start at `(sx, sy)` at time 0. At each second, we explore all 8 adjacent cells from the cells we could reach in the previous second. If at exactly time `t`, one of the reachable cells is `(fx, fy)`, we return true.
**Time:** O(8^t). At each step `k`, we can reach up to `8^k` new cells. · **Space:** O(8^t). The queue and visited set can grow exponentially.
**Pros:** Conceptually simple and directly models the problem statement.
**Cons:** Extremely inefficient. The time and space complexity are exponential in `t`, making it infeasible for the given constraints.; `t` can be up to `10^9`, so a simulation is impossible.; Storing visited states with large coordinates requires a hash-based set, which has overhead.
### Explanation
The state in our search can be represented by `(x, y, time)`. We start with a queue containing the initial state `(sx, sy, 0)`. We also need a way to keep track of visited states `(x, y, time)` to avoid cycles and redundant work. A hash set is needed due to the large coordinate values.

The BFS proceeds level by level, where each level corresponds to one second of time. In each step, we dequeue a state `(curr_x, curr_y, curr_time)`. If `curr_time == t`, we check if we are at the destination. If `curr_time < t`, we generate all 8 adjacent cells and enqueue them for the next time step if they haven't been visited at that specific time. This approach is not feasible given the constraints `t <= 10^9` because the number of reachable cells grows exponentially with time.
### Algorithm
*   Initialize a queue and add the starting state `(sx, sy, 0)`.
*   Initialize a set `visited` to store `(x, y, time)` tuples to avoid redundant exploration. Add `(sx, sy, 0)` to `visited`.
*   While the queue is not empty:
    *   Dequeue the current state `(x, y, time)`.
    *   If `time == t`:
        *   If `x == fx` and `y == fy`, return `true`.
        *   Continue to the next state in the queue.
    *   If `time > t`, stop exploring this path.
    *   For each of the 8 neighbors `(nx, ny)` of `(x, y)`:
        *   If `(nx, ny, time + 1)` is not in `visited`:
            *   Add `(nx, ny, time + 1)` to `visited`.
            *   Enqueue `(nx, ny, time + 1)`.
*   If the loop finishes, it means `(fx, fy)` was not reached at exactly time `t`. Return `false`.

## Constant Time Mathematical Approach
Instead of simulating the movement, we can solve this problem by analyzing the properties of movement on the grid. The key insight is to determine the minimum time required to travel between the start and end cells and then consider how any extra time can be spent.
**Time:** O(1). The solution involves a few arithmetic operations and comparisons, which take constant time. · **Space:** O(1). No extra space is used that depends on the input size.
**Pros:** Extremely efficient with constant time and space complexity.; Handles all edge cases correctly.; Works for the large constraints given in the problem.
**Cons:** The logic is not immediately obvious and requires some mathematical reasoning about grid movement.
### Explanation
The minimum number of moves to get from `(sx, sy)` to `(fx, fy)` is determined by the Chebyshev distance, which is `max(|sx - fx|, |sy - fy|)`. This is because in one move (one second), we can cover at most one unit of distance in the x-direction and one unit in the y-direction (with a diagonal move). To cover a total horizontal distance of `dx = |sx - fx|` and vertical distance of `dy = |sy - fy|`, we need at least `max(dx, dy)` moves. Let this be `min_time`.

The problem can be broken down into two main cases:

1.  **Start and Finish cells are the same (`sx = fx`, `sy = fy`):**
    *   In this case, `dx = 0` and `dy = 0`, so `min_time = 0`.
    *   If `t = 0`, we are already at the destination. It's possible.
    *   If `t = 1`, we *must* move to an adjacent cell, so we cannot be at the starting cell. It's impossible.
    *   If `t >= 2`, we can spend the time by moving to an adjacent cell and then moving back. This takes 2 seconds. It's possible for any `t` except `t=1`.

2.  **Start and Finish cells are different:**
    *   The minimum time required is `min_time = max(dx, dy)`.
    *   If the given time `t` is less than `min_time`, it's impossible to reach the destination.
    *   If `t >= min_time`, we can always reach the destination. We can arrive in `min_time` seconds using an optimal path. Any extra time `t - min_time` can be "wasted" by taking small detours or moving back-and-forth from the destination. Thus, if `t >= min_time`, it's always possible.

Combining these observations gives a simple and efficient algorithm.

```java
class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int dx = Math.abs(sx - fx);
        int dy = Math.abs(sy - fy);

        if (dx == 0 && dy == 0) {
            // If start and end are the same, we can't reach in exactly 1 second
            // because we must move. For any other time t != 1, it's possible.
            return t != 1;
        }

        int minTime = Math.max(dx, dy);
        
        // If we are not at the same cell, we must take at least minTime steps.
        return t >= minTime;
    }
}
```
### Algorithm
*   Calculate the horizontal distance `dx = |sx - fx|`.
*   Calculate the vertical distance `dy = |sy - fy|`.
*   Check for the special case where the start and end points are the same (`dx == 0` and `dy == 0`).
    *   If they are the same, return `true` if `t` is not equal to 1, and `false` otherwise. This is because we must move each second, so we can't stay at the same spot at `t=1`. For `t=0` we are already there, and for `t>=2` we can move away and come back.
*   If the points are different, calculate the minimum time required, which is the Chebyshev distance: `min_time = max(dx, dy)`.
*   Return `true` if the given time `t` is greater than or equal to `min_time`, and `false` otherwise. Any time `t >= min_time` is achievable.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool IsReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy) return t != 1;
        return Math.Max(Math.Abs(sx - fx), Math.Abs(sy - fy)) <= t;
    }
}
```

### Java

```java
class Solution {
public
  boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
    if (sx == fx && sy == fy) {
      return t != 1;
    }
    int dx = Math.abs(sx - fx);
    int dy = Math.abs(sy - fy);
    return Math.max(dx, dy) <= t;
  }
}

```

### Python

```python
class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool: if sx == fx and sy == fy: return t != 1 dx = abs(sx - fx) dy = abs(sy - fy) return max(dx, dy) <= t

```

### CPP

```cpp
class Solution {
public:
  bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
    if (sx == fx && sy == fy) {
      return t != 1;
    }
    int dx = abs(fx - sx), dy = abs(fy - sy);
    return max(dx, dy) <= t;
  }
};

```