Серия ежедневных вопросов leetcode - Побег от препятствия - "Манхэттенское расстояние"

задняя часть алгоритм
Серия ежедневных вопросов leetcode - Побег от препятствия - "Манхэттенское расстояние"

Это 22-й день моего участия в августовском испытании обновлений.Подробности о событии:Испытание августовского обновления

leetcode-789 - блокировщик выхода

[ссылка на блог]

Путь обучения Цая🐔

Наггетс Главная

[Название Описание]

Вы играете в упрощенную версию Pac-Man. Вы начинаете с [0, 0] и конечным пунктом является target = [xtarget, ytarget] . На карте есть блокираторы, В виде массива ghosts i-й ​​блокировщик начинается с ghosts[i] = [xi, yi]. Все входные данные представляют собой целые координаты.

Каждый ход вы и блокирующие можете двигаться на восток, запад, юг и север одновременно, каждый раз перемещаясь в новое место на 1 единицу дальше от исходного места. Конечно, вы также можете не двигаться. Все действия происходят одновременно .

Побег считается успешным, если вы можете добраться до пункта назначения до того, как вас поймают блокирующие (блокирующие могут предпринять любые действия). Если вы и блокирующий доберетесь до одного и того же места (включая пункт назначения) одновременно, это не считается побегом. успех.

Выведите true, только если у вас есть шанс сбежать, в противном случае выведите false.

Пример 1:

输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。

Пример 2:

输入：ghosts = [[1,0]], target = [2,0]
输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。

Пример 3:

输入：ghosts = [[2,0]], target = [1,0]
输出：false
解释：阻碍者可以和你同时达到目的地。

Пример 4:

输入：ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7]
输出：false

Пример 5:

输入：ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]], target = [0,0]
输出：true

намекать:

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • -10⁴
  • В одном месте может быть несколько блокировщиков
  • target.length == 2
  • 10⁴

Related Topics

  • Манхэттенское расстояние
  • жадный

[Название ссылки]

ссылка на тему литкода

[адрес гитхаба]

ссылка на код

[Введение в идеи]

Идея 1: Манхэттенское расстояние

  • dis[A,B] означает от A до BМанхэттенское расстояние
  • dis[A,B] = ∣xa−xb∣−∣ya−yb∣|x_{a}-x_{b}|-|y_{a}-y_{b}|;
  • Этот вопрос спрашивает, больше ли манхэттенское расстояние от всех элементов призрачного массива до цели, чем манхэттенское расстояние от (0,0) до цели.
  • Я хорошо понимаю можно ли его перехватить у цели, а можно ли перехватить у целиПромежуточный перехватЭто должно быть доказано контр доказательствами
  • процесс доказывания:
    • Мы предполагаем, что есть некоторая точкаGСделать dis[G,X]Gпризрак может быть в какой-то момент посреди путиXперехватывать
    • dist[G,X] + dis[X,T] <= dis[S,X] + dis[X,T]
    • dist[G,X] + dis[X,T] <= dis[S,T]
    • dist[G,T] <= dist[G,X] + dist[X,T] <= dist[S,T]
  • Вопреки предыдущему утверждению **dis[G,T] > dis[S,T]**
  • Поэтому он может разрешить
public boolean escapeGhosts(int[][] ghosts, int[] target) {
    int dis = Math.abs(target[0]) + Math.abs(target[1]);
    for (int[] ghost:ghosts
         ) {
        int x = ghost[0], y = ghost[1];
        if (Math.abs(x-target[0]) + Math.abs(y-target[1]) <= dis){
            return false;
        }
    }
    return true;

}
  • Временная сложность O (n)
  • Пространственная сложность O(1)
Категории