从零学算法2849

2849.给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。
在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你 必须 移动到任一与之前所处单元格相邻的单元格中。
如果你能在 恰好 t 秒 后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。
单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。
示例 1：
输入：sx = 2, sy = 4, fx = 7, fy = 7, t = 6
输出：true
解释：从单元格 (2, 4) 开始出发，可以在恰好 6 秒后到达单元格 (7, 7) 。
示例 2：
输入：sx = 3, sy = 1, fx = 7, fy = 3, t = 3
输出：false
解释：从单元格 (3, 1) 开始出发，至少需要 4 秒后到达单元格 (7, 3) 。 因此，无法在 3 秒后到达单元格 (7, 3) 。

• 我的思路：不用想的太复杂，其实根据它可重复到达单元格以及可移动到任一相邻单元格的特性，只要给你的时间 t 大于等于至少所需时间，就能到达。
• 至少所需时间：首先起点到终点经过转换都能看成 (0,0) 到达 (x,y)，并且到 (x,y) 和到 (-x,y),(x,-y),(-x,-y) 都是一样的。所以比如 (0,0) 到 (2,3)，最快的移动方式肯定是先到 (1,1) ，然后到 (2,2)，最后到 (2,3)。因为同样从 (0,0) 到 (1,1)，直线行走至少需要 2 秒，斜着走只需要 1 秒，所以肯定是能斜着走就斜着走。所以至少所需秒数其实就是斜着的 2 秒加上剩下的 3-2 秒。相加其实不就是 3，所以至少需要 max(x,y) 秒。但是还有一种特殊情况，就是如果起点就在终点，这时候再给你一秒，那你往哪走都回不来了，所以还需要特判这种情况。

•   public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
    	// fx-sy,fy-sy：转换为 (0,0) -> (x,y)
    	// abs()：上面说了 (0,0) -> (x,y) 和 (0,0) -> (-x,-y) 至少需要的秒数一样	
        int x = Math.abs(fx-sx);
        int y = Math.abs(fy-sy);
        int min = x<y?y:x;
        // 不在起点，并且给你的时间大于至少所需时间 || 在起点，给你的不是 1 秒
        return (min>0 && t>=min) || (min==0 && t!=1);
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9