Найти кратчайший путь для достижения заданной ячейки назначения в 2D матрице с препятствиями - PullRequest
Новая
       57

Найти кратчайший путь для достижения заданной ячейки назначения в 2D матрице с препятствиями

0 голосов
/ 20 ноября 2018

Я работаю над вопросом ниже, и я не совсем понимаю, как использовать поиск BFS здесь.Я не понимаю, как бороться с блокировками здесь?

Учитывая матрицу MxN, найдите кратчайший путь для достижения данной целевой ячейки.Робот может двигаться вверх, вниз, влево или вправо.Матрица также поставляется с набором блокировок в нескольких ячейках, через которые робот не может пройти.Выведите минимальное количество ходов, которое должен сделать робот, чтобы добраться до пункта назначения.Выведите -1, если пункт назначения недоступен.Предположим, что блокада никогда не будет в начальной ячейке.

Формат ввода: Первая строка содержит значения матрицы M и N.Вторая строка содержит местоположение ячейки стартовой позиции роботов.Третья строка содержит местоположение ячейки пункта назначения.Четвертая строка и следующие за ней строки будут содержать местоположения блокад.Пример ниже содержит только одну блокаду в (2,2), через которую робот не может пройти.Ниже приведен ввод: 

3 3
1 1
3 3
2 2

Для вышеприведенного ввода должно быть 4 вывода.

Ниже приведено то, что я начал, но запутался в том, как бороться с блокадой при выполнении поиска BFS.: 

  public static void main(String args[] ) throws Exception {
    Scanner sc = new Scanner(System.in);
    int M = sc.nextInt();
    int N = sc.nextInt();

    int startX = sc.nextInt();
    int startY = sc.nextInt();

    int destinationX = sc.nextInt();
    int destinationY = sc.nextInt();

    while (sc.hasNext()) {
        int blockedX = sc.nextInt();
        int blockedY = sc.nextInt();
    }
}

1 Ответ

0 голосов
/ 20 ноября 2018

Вы можете просто просмотреть сетку в виде графика: каждая ячейка подключена к своим четырем соседям (или меньше, если она на краю), исключая любые блокировки.Используя ваш пример: 

  1 2 3
1 • • •
2 • x •
3 • • •

у нас есть график (с использованием нотации (строка, столбец)): 

(1,1) <-> (1,2)
(2,1) <-> (3,1)
(3,1) <-> (2,3)
(2,3) <-> (3,3)
(3,3) <-> (3,2)
(3,2) <-> (3,1)
(3,1) <-> (2,1)
(2,1) <-> (1,1)

, где все длины ребер равны 1. Теперь вы можете применить стандарт BFS от начального узла до достижения целевого узла, отслеживая, какие узлы вы посещаете.В псевдокоде:

  • Пометить все расстояния между ячейками как бесконечные, за исключением начальной ячейки робота с нулевым расстоянием (вы можете сделать это, используя дополнительный 2D-массив, или, возможно, даже на месте, в зависимости от того, как высохранить сетку).
  • Инициализировать пустую очередь ячеек Q
  • Добавить начальную ячейку робота в Q
  • Пока Q не пусто:
    • Удаление из очередиследующая ячейка C из Q
    • Для каждого неблокирующего соседа N из C (легко определить по сетке):
      • Если расстояние N равно бесконечности, отметьте расстояние N как (расстояние C)+ 1, и добавьте N к Q.
      • Если N является ячейкой назначения, верните расстояние N.
  • На данный момент мы знаем, что естьнет пути от начальной ячейки к ячейке назначения.
...