Кодовые войны: поиск пути

Задача

Вы на позиции [0, 0] в лабиринте NxN, и вы можете двигаться только в одном из четырех сторон света (т.е. север, восток, юг, запад). Верните истину, если вы можете достичь позиции [N-1, N-1] или ложь в противном случае.

  • Отмечены пустые позиции.
  • Стены обозначены буквой W.
  • Позиции начала и выхода пусты во всех тестовых случаях.

Я знаю, что это уже существует, но мое решение немного другое, так что …

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

  1. Как остановить рекурсию после нахождения решения
  2. Перед добавлением массива “посещенных” я модифицировал массив лабиринта на каждом ходу: maze = maze.slice (0, pos) + ‘p’ + maze.slice (pos + 1). Добавление пространственной сложности (“посещенный” массив) РЕШИЛИ МНОГО.
  3. Преобразование [x, y] <=> userPosition, поскольку изначально лабиринт представляет собой чистую строку. Я обнаружил, что это преобразование (деление, модуль) даже не требуется. Это улучшение что-то значит?

Решение:

"use strict";

function pathFinder(maze) {
  const size = maze.split("n")[0].length;
  const visited = new Array((size + 1) * size);
  return solveMaze(maze, visited, size, 0);
}

function solveMaze(maze, visited, size, userPosition){
  
  if (userPosition === maze.length - 1) {
    return true;
  } else {
    
    let result;
    visited[userPosition] = true;
    
    const allSteps = [userPosition - (size + 1), //up
                    userPosition + 1,    //right
                    userPosition + (size + 1),  //down
                    userPosition - 1];   //left

    const possibleSteps = allSteps.filter(pos => pos > 0 && 
                   pos < maze.length && 
                   maze[pos] !== 'W' && 
                   !visited[pos] && 
                   maze[pos] !== 'n');
    
    for (const step of possibleSteps) {
      result = solveMaze(maze, visited, size, step);
      if (result) return result;
    }
    return false;
  }
}

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *