Это определенно один из наиболее часто задаваемых вопросов на любом собеседовании по программированию! Самое смешное, что этот вопрос часто искажают и задают разными способами. Но основа решения остается прежней. Это будет вариант поиска в ширину (BFS).

Молодых программистов часто пугает идея реализовать BFS и найти это идеальное решение. Но использование этого алгоритма не должно быть очень страшным. На самом деле все намного проще, чем вы думаете.

Вот простое видео на YouTube, которое поможет вам решить эту проблему с помощью BFS.

Решение проблемы!

Псевдокод

  1. Найдите размер сетки
  2. Временно сохранить информацию о текущем местоположении.
  3. Создайте очередь, укажите местоположение непосещаемых ячеек.
  4. Проверить, совпадает ли текущее местоположение с местом назначения. Если да, верните текущее местоположение.
  5. Найдите соседей для текущего местоположения.
  6. Если сосед не посещен, поместите местоположение в очередь, повторите шаги с 4 по 5
  7. Если место назначения не достигнуто и очередь пуста, вернуть false.

Фактические строки кода

Построение сетки, определение размера строки и столбца

Прежде всего, необходимо построить сетку. Здесь каждая ячейка - это объект, содержащий информацию о состоянии. Состояние может быть пусто, заблокировано, посещено или цель.

let grid = [
[{state:'empty'},{state:'empty'},{state:'empty'}],
[{state:'empty'},{state:'block'},{state:'goal'}]]

Далее нам нужно определить начальную и конечную ячейки.

let start = [0,0];
let end = [1,2];

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

let row = grid.length;
let col = grid[0].length;

Начальное местоположение магазина

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

findPath = function(){
   var location = {r: start[0],c: start[1] };
}

Очередь

Большая часть алгоритма BFS реализована с использованием структуры данных очереди. В Javascript очередь, на которую мы ссылаемся, тоже будет массивом. И первый элемент, который будет нажат, должен быть «начальной» ячейкой.

var queue = [];
queue.push(location);

Петля

Как только очередь готова и начальная ячейка вставлена, цикл, который проверяет, достигнута ли цель, может быть выполнен. Цикл выполняется до тех пор, пока в очереди есть элемент.

shift () используется для удаления первого элемента в очереди и перемещения оставшихся элементов вниз на один индекс.

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

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

while(queue.length){
   var currentLocation = queue.shift();
   if(currentLocation.r == end[0] && currentLocation.c == end[1])
       return currentLocation;
   grid[currentLocation.r][currentLocation.c].state == 'visited'
}

Соседи

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

exploreLocation= function(location){
let r = location.r;
let c = location.c;
let allNeighbors = [];
//left
if (safeNeighbor(r, c - 1)) allNeighbors.push({ r: r, c: c - 1 });
//right
if (safeNeighbor(r, c + 1)) allNeighbors.push({ r: r, c: c + 1 });
//top
if (safeNeighbor(r - 1, c)) allNeighbors.push({ r: r - 1, c: c });
//bottom
if (safeNeighbor(r + 1, c)) allNeighbors.push({ r: r + 1, c: c });
return allNeighbors;
}

Функция safeNeighbor () проста. Это гарантирует, что проверяемая ячейка находится внутри сетки.

safeNeighbor = function (r, c) {
if (r < 0 || r >= row) return false;
if (c < 0 || c >= col) return false;
if (grid[r][c].state == 'block') return false;
return true;
};

Обработка непосещенных ячеек

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

var neighbors = exploreLocation(currentLocation);
for(neighbor of neighbors){
  if(grid[neighbor.r][neighbor.c].state != "visited")
  {
    queue.push(neighbor);
    grid[neighbor.r][neighbor.c]["parent"]=currentLocation;
  }
}

В цикле for используется «из» вместо «внутри». Почему? For… of выполняет итерацию по значениям массива. For… in выполняет итерацию по перечислимым свойствам массива, затем эти свойства можно использовать для идентификации значений.

Собираем код:

Ссылка на Github: https://github.com/CodeLearnDDev/basicJS.git; файл: path_between_cells_in_JS

let grid = [
[{ state: 'empty' }, { state: 'empty' }, { state: 'empty' }],
[{ state: 'empty' }, { state: 'block' }, { state: 'goal' }],
];
let start = [0, 0];
let end = [1, 2];
let row = grid.length;
let col = grid[0].length;
safeNeighbor = function (r, c) {
if (r < 0 || r >= row) return false;
if (c < 0 || c >= col) return false;
if (grid[r][c].state == 'block') return false;
return true;
};
exploreLocation = function (location) {
let r = location.r;
let c = location.c;
let allNeighbors = [];
//left
if (safeNeighbor(r, c - 1)) allNeighbors.push({ r: r, c: c - 1 });
//right
if (safeNeighbor(r, c + 1)) allNeighbors.push({ r: r, c: c + 1 });
//top
if (safeNeighbor(r - 1, c)) allNeighbors.push({ r: r - 1, c: c });
//bottom
if (safeNeighbor(r + 1, c)) allNeighbors.push({ r: r + 1, c: c });
return allNeighbors;
};
findPath = function () {
var location = {
r: start[0],
c: start[1],
};
var queue = [];
queue.push(location);
while (queue.length) {
var currentLocation = queue.shift();
if (currentLocation.r == end[0] && currentLocation.c == end[1])
return currentLocation;
grid[currentLocation.r][currentLocation.c].state = 'visited';
var neighbors = exploreLocation(currentLocation);
for(neighbor of neighbors)
{
  if(grid[neighbor.r][neighbor.c].state != "visited")
  {
    queue.push(neighbor);
    grid[neighbor.r][neighbor.c]["parent"]=currentLocation;
  }
}
}
return false;
};
findPath()

Печать пути

Распечатать путь не составит труда, потому что каждая ячейка содержит подробную информацию о своей родительской ячейке. Нам просто нужно просмотреть эту информацию.

printPath = function(path){
 let paths = [path];
 while(true){
 let r = path.r;
 let c = path.c;
 let parent = grid[r][c].parent;
 if(parent == undefined)
   break;
 paths.push(parent);
 path = {r:parent.r,c:parent.c};
 }
console.log(paths)
}

Вывод

Выполнив эти строки кода, вы должны получить следующий результат:

{0,0},{0,1},{0,2},{1,2}

Заключение!

Спасибо, что прочитали мою статью, надеюсь, вам было интересно. Пожалуйста, оставьте свои комментарии ниже! Вот несколько полезных ссылок:

Код в GitHub: https://github.com/CodeLearnDDev/basicJS.git

Учебник на YouTube: https://youtu.be/PnSy9Ef1TGg