Determine if a Cell Is Reachable at a Given Time

Problem Statement

The task is to determine whether it's possible to exactly reach a destination point (fx, fy) from a starting point (sx, sy) in an infinite 2D grid after exactly t seconds. At each second, movement to any of the eight adjacent cells surrounding the current location is possible. A pivotal consideration is that each move takes one exact second, and you are allowed to visit the same cell multiple times. The decision to be made is whether you can land on (fx, fy) right at the t-th second.

Examples

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

Approach and Intuition

1. To begin solving the problem, it's necessary first to determine the Manhattan distance between the start (sx, sy) and the finish (fx, fy) positions. The Manhattan distance provides the minimum steps required to travel between two points when movement is restricted to grid lines.

   • The calculation is based on the formula: min_steps = abs(fx - sx) + abs(fy - sy).

2. Using this minimum number of steps (min_steps), approximate if it's feasible to make these steps within the given time t.

   • If min_steps is more significant than t, it's impossible to reach (fx, fy) in time because we don't have enough seconds.
   • If min_steps is less than or equal to t, further considerations take effect.

3. Account for the number of additional moves needed if min_steps is less than t. To land exactly on (fx, fy) after t seconds:

   • The additional moves (t - min_steps) should allow one to formulate a sequence that ultimately permits an exact (fx, fy) landing at t seconds.
   • These excess moves, because every extra move requires a returning move to keep you in a possible path to reach the destination exact after t moves, must be such that they are compensated by a subsequent reversing or nullifying move.

4. A crucial observation:

   • As the movement forms a Manhattan grid and moving back and forth or up and down between two cells doesn't change the net distance covered, t must have the same parity (even or odd) as min_steps. This ensures that any surplus time can be used effectively to simulate stationary movement (moving to a cell and moving back) which does not change the position but consumes time.

To determine reachability:

• Calculate min_steps
• Compare min_steps with t to see if it's feasible to even consider reaching (fx, fy)
• Check if t - min_steps, if even or odd, matches the evenness or oddness of the path length. This ensures that you can use any extra time without ending up away from (fx, fy).

Understanding through examples:

• For Example 1 with inputs (sx = 2, sy = 4, fx = 7, fy = 7, t = 6): The minimum steps to reach (7, 7) from (2, 4) are 8 (5+3), but one can manipulate movements using remaining negative surplus moves to remain stationary, effectively using the time and reaching the destination exactly at t = 6.
• For Example 2 with inputs (sx = 3, sy = 1, fx = 7, fy = 3, t = 3): The minimum steps are 6 (4+2), and with only 3 seconds available, there's no tactical way to negate the extra moves required.

This concept leverages grid properties and parity characteristics of even and odd numbers to ascertain exactness in movement and timing, key to solving the problem efficiently and correctly.

Solutions

class Solution {
public:
    bool canReachDestination(int startX, int startY, int finalX, int finalY, int time) {
        int deltaX = abs(startX - finalX);
        int deltaY = abs(startY - finalY);
        if (deltaX == 0 && deltaY == 0 && time == 1) {
            return false;
        }
        return time >= max(deltaX, deltaY);
    }
};