13
Мар
2020

Задача про ловушку. Алгоритм поиска пути

Спроектирован робот который несет бремя из точки A в точку B.

Чтобы протестировать робота была выбрана матрица размером n x m, по которой робот должен передвигаться из точки (0, 0) к точке (n, m).

Робот имеет два варианта для продвижения, сверху вниз и справа налево.

Если значение поля i, j матрицы равно -1, это значит, что там находится ловушка, которая может навредить роботу. Что, в свою очередь, означает, что робот не может наступить на это поле.

Нужно написать функцию которая получает матрицу и вернет true, если робот сможет из точки (0, 0) дойти до точки (n, m), а в противоположном случае false.

Например

A = [
    [0, 0, 0, -1, 0],
    [-1, 0, 0, -1, -1],
    [0, 0, 0, -1, 0],
    [-1, 0, 0, 0, 0],
    [0, 0, -1, 0, 0]
]

B = [
    [0, 0, -1],
    [0, -1, -1],
    [-1, -1, 0]
]

Робот сможет дойти до конечной в случае матрицы A, а в случае B не сможет.

console.log([
               [0, 0, 0, -1, 0],
               [-1, 0, 0, -1, -1],
               [0, 0, 0, -1, 0],
               [-1, 0, 0, 0, 0],
               [0, 0, -1, 0, 0]
            ]);   // true

console.log([
              [0, 0, -1],
              [0, -1, -1],
              [-1, -1, 0]
            ]);  // false

console.log([
              [0, 0, 0], 
              [0, 0, 0], 
              [0, 0, 0]
           ]);     // true

console.log([
              [0, 0, 1], 
              [1, 0, -1], 
              [0, -1, 0]
            ]);  // false

Поможете решить задачу?

Источник: https://ru.stackoverflow.com/questions/1094311/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0-%D0%BF%D1%80%D0%BE-%D0%BB%D0%BE%D0%B2%D1%83%D1%88%D0%BA%D1%83-%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0-%D0%BF%D1%83%D1%82%D0%B8
Share

Тебе может это понравится...