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