Determine if a Cell Is Reachable at a Given Time

Determine if a Cell Is Reachable at a Given Time - Problem

Math Medium

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.

Input & Output

Example 1 — Cannot Reach in Time

$ Input: sx = 2, sy = 1, fx = 4, fy = 3, t = 3

› Output: false

💡 Note: Minimum distance is max(|4-2|, |3-1|) = max(2,2) = 2. We need exactly 3 seconds, but after reaching in 2 seconds, we have 1 second left (odd). We can't waste exactly 1 second with back-and-forth movement.

Example 2 — Perfect Timing

$ Input: sx = 1, sy = 1, fx = 1, fy = 1, t = 3

› Output: true

💡 Note: Start and target are the same. Since t=3 is odd and we need to move each second, we can move to an adjacent cell and return (takes 2 seconds), then move away and back again (1 more second).

Example 3 — Insufficient Time

$ Input: sx = 1, sy = 1, fx = 5, fy = 5, t = 3

› Output: false

💡 Note: Minimum distance is max(|5-1|, |5-1|) = max(4,4) = 4 seconds. We only have 3 seconds available, so it's impossible to reach the target.

Constraints

1 ≤ sx, sy, fx, fy ≤ 10⁹
0 ≤ t ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Start position, target position, and exact time limit

Calculate

Find minimum distance using Chebyshev metric

Verify

Check if timing constraints can be satisfied

Key Takeaway

🎯 Key Insight: Chebyshev distance gives minimum time, remaining time must be even for back-and-forth movement

Asked in

G Google 28 M Microsoft 22 🍎 Apple 15 M Meta 12

The key insight is using Chebyshev distance - the minimum time to reach target (fx,fy) from (sx,sy) is max(|fx-sx|, |fy-sy|) because we can move diagonally. The remaining time must be even to allow back-and-forth movement. Best approach is the mathematical solution with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized BFS (Level-wise)	O(8^t)	O(8^t)	Use BFS with time tracking to find exact timing
Mathematical Solution - Chebyshev Distance	O(1)	O(1)	Calculate minimum distance and check timing constraints
Brute Force - Try All Paths	O(8^t)	O(t)	Generate all possible 8^t paths using recursion

Optimized BFS (Level-wise) — Algorithm Steps

Initialize BFS queue with starting position and time 0
For each second, expand all current positions
Use set to track visited positions at current time
Return true if target is reached exactly at time t

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with position (sx,sy) at time 0

Expand

Each second, explore 8 adjacent positions

Check

At time t, see if target position is reached

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 1000000

typedef struct {
    int x, y, time;
} State;

State queue[MAX_QUEUE_SIZE];
int front = 0, rear = 0;

void push(int x, int y, int time) {
    queue[rear++] = (State){x, y, time};
}

State pop() {
    return queue[front++];
}

bool isEmpty() {
    return front >= rear;
}

bool solution(int sx, int sy, int fx, int fy, int t) {
    if (t == 0) {
        return sx == fx && sy == fy;
    }
    
    // Simple BFS (without visited set for simplicity)
    front = 0;
    rear = 0;
    push(sx, sy, 0);
    
    while (!isEmpty()) {
        State current = pop();
        
        if (current.time == t) {
            if (current.x == fx && current.y == fy) {
                return true;
            }
            continue;
        }
        
        // Try all 8 adjacent cells (limited exploration to prevent timeout)
        if (current.time < 10) {  // Limit depth for practical purposes
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    push(current.x + dx, current.y + dy, current.time + 1);
                }
            }
        }
    }
    
    return false;
}

int main() {
    int sx, sy, fx, fy, t;
    scanf("%d", &sx);
    scanf("%d", &sy);
    scanf("%d", &fx);
    scanf("%d", &fy);
    scanf("%d", &t);
    bool result = solution(sx, sy, fx, fy, t);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(8^t)

In worst case, we explore all possible positions reachable in t seconds

✓ Linear Growth

Space Complexity

O(8^t)

BFS queue and visited set can contain up to 8^t positions

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized BFS (Level-wise) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler