Вы на позиции [0, 0] в лабиринте NxN, и вы можете двигаться только в одном из четырех сторон света (т.е. север, восток, юг, запад). Верните истину, если вы можете достичь позиции [N-1, N-1] или ложь в противном случае.
- Отмечены пустые позиции.
- Стены обозначены буквой W.
- Позиции начала и выхода пусты во всех тестовых случаях.
Я знаю, что это уже существует, но мое решение немного другое, так что …
Это очень круто, и я вижу, что у людей много проблем из-за производительности (тесты большие). У меня здесь было 3 проблемы:
- Как остановить рекурсию после нахождения решения
- Перед добавлением массива «посещенных» я модифицировал массив лабиринта на каждом ходу: maze = maze.slice (0, pos) + ‘p’ + maze.slice (pos + 1). Добавление пространственной сложности («посещенный» массив) РЕШИЛИ МНОГО.
- Преобразование [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;
}
}