Last Updated on 2023-11-08 by Clay
題目
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 <= 109
題目給定了 (sx, sy) 的起始點，並讓我們判斷是否能夠在時間 t 時剛好抵達 (fx, fy) 的終點。
解題思路
由於我們移動的方式是可以水平、垂直以及斜著移動，所以我們從起點抵達終點的最短步數可以表示成 max(|sx-fx|, |sy-fy|) —— 這是因為我們可以斜走的關係，而在假設在水平跟垂直方向總有一個比較近、並且我們可以斜著移動（同時走水平和垂直）的情況下，我們自然只需要移動距離比較遠的那個方向的距離。
而由於題目要求我們需要在時間 t 時剛好抵達終點，所以只要最大距離小於 t，不管小於多少，我們都能夠透過浪費任意步數來剛好在時間 t 時抵達。
唯一需要注意的例外是：如果一開始起點跟終點就是相同的，並且要求要在時間 t=1 的情況下抵達，我們就會失敗！
所以寫好例外狀況後，這題就沒有任何難度了。
複雜度
| Time Complexity | O(1) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
// Base case
if (sx == fx && sy == fy && t == 1) {
return false;
}
// Init
int dx = abs(sx - fx);
int dy = abs(sy - fy);
// Check
t -= max(dx, dy);
return t >= 0;
}
};Python 範例程式碼
class Solution:
def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
# Base case
if (sx, sy) == (fx, fy) and t == 1:
return False
# Init
dx = abs(sx - fx)
dy = abs(sy - fy)
# Check
t -= max(dx, dy)
return t >= 0