Solution1 贪心 + 曼哈顿距离

• 时间复杂度 $O(n)$

  n 为 ghosts 的数量

• 空间复杂度 $O(1)$

结论：「如果一个阻碍者能够抓到玩家，必然不会比玩家更晚到达终点」

证明：

设玩家起点、阻碍着起点、终点分别为 s, e, t。

设玩家从 s 到 t 会经过点 k。当且仅当 dist(e, k) <= dist(s, k)，时，阻碍者会在 k 点抓到玩家。

由于 k 到 t 为公共部分，所有能抓到玩家时，有

dist(e, k) + dist(k, t) <= dist(s, k) + dist(k, t)

->

dist(e, t) <= dist(s, t)

由于都是方格，且不能斜着移动，所以转化为曼哈顿距离