Рубрики

Минимальные прыжки блока, чтобы добраться до места назначения

Задано N линий и одна начальная точка и точка назначения в 2-мерном пространстве. Эти N строк делят пространство на несколько блоков. Нам нужно напечатать минимальное количество прыжков, чтобы достичь пункта назначения от начальной точки. Мы можем перейти с одного блока на другой, только если они имеют общую сторону.
Примеры:

Input : Lines = [x = 0, y = 0, x + y – 2 = 0]
        Start point = [1, 1], 
        Dest point  = [-2, -1]
Output : 2        
We need to jump 2 times (B4 -> B3 then B3 -> B5 
or B4 -> B6 then B6 -> B5) to reach destination 
point from starting point shown in below diagram. 
Each block i is given an id Bi in the diagram.

Мы можем решить эту проблему, используя свойство линий и точек, которое задается следующим образом: если мы поместим две точки в уравнение линии, то они будут иметь один и тот же знак, то есть положительно-положительный или отрицательно-отрицательный оценочного значения, если обе точки лежат на одной стороне линии, в случае разного знака, то есть положительного-отрицательного, они будут лежать на другой стороне линии.
Теперь мы можем использовать свойство выше для решения этой проблемы. Для каждой строки мы будем проверять, находятся ли начальная и конечная точки на одной стороне или нет. Если они лежат на другой стороне линии, то эта линия должна быть пересечена, чтобы приблизиться. Как и в приведенной выше диаграмме, начальная точка и точка назначения находятся на одной стороне линии x + y — 2 = 0, поэтому не нужно пересекать эту линию, остальные две линии необходимо пересечь, поскольку обе точки находятся на противоположной стороне.
Наконец, мы проверим знак оценки точек по каждой линии и будем увеличивать количество прыжков всякий раз, когда обнаруживаем противоположные знаки. Общая временная сложность этой задачи будет линейной.

// C ++ программа для поиска минимальных прыжков для достижения
// заданный пункт назначения из заданного источника
#include <bits/stdc++.h>

using namespace std;

  
// Представить точку в 2D пространстве

struct point

{

    int x, y;

    point(int x, int y) : x(x), y(y)

    {}

};

  
// Представляем строку формата (ax + by + c)

struct line

{

    int a, b, c;

    line(int a, int b, int c) : a(a), b(b), c(c)

    {}

    line()

    {}

};

  
// Возвращает 1, если оценка больше> 0,
// иначе возвращает -1

int evalPointOnLine(point p, line curLine)

{

    int eval = curLine.a* p.x +

               curLine.b * p.y +

               curLine.c;

    if (eval > 0)

        return 1;

    return -1;

}

  
// Возвращает минимальные прыжки для достижения
// пункт назначения от начальной точки

int minJumpToReachDestination(point start,

              point dest, line lines[], int N)

{

    int jumps = 0;

    for (int i = 0; i < N; i++)

    {

        // получаем знак оценки из точки

        // координата и линейное уравнение

        int signStart = evalPointOnLine(start, lines[i]);

        int signDest = evalPointOnLine(dest, lines[i]);

  

        // если обе оценки имеют противоположный знак,

        // увеличить прыжок на 1

        if (signStart * signDest < 0)

            jumps++;

    }

  

    return jumps;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    point start(1, 1);

    point dest(-2, -1);

  

    line lines[3];

    lines[0] = line(1, 0, 0);

    lines[1] = line(0, 1, 0);

    lines[2] = line(1, 1, -2);

  

    cout << minJumpToReachDestination(start, dest, lines, 3);

  

    return 0;

}

Выход:

2

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальные прыжки блока, чтобы добраться до места назначения

0.00 (0%) 0 votes