Решаем задачу с собеседования по JS про лабиринт | Maze

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

Даже эта задача имеет множество различных алгоритмов решений, мы рассмотрим вариант с рекурсией.

Мне попадалась эта задача в очень разных интерпретациях, одна из них была поставлена, как будто бы лабиринт – это полупроводниковая дорожка, по которой может протекать ток, но по этой дорожке разбросаны дефекты, как пиксели. По ним ток не течет. И необходимо понять: при данном расположении дефектов проводит ли эта дорожка сигнал.

---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
---

Присоединяйтесь к нам в соцсетях:


#leetcode, #алгоритмы, #javascript #itсобеседование

[frontendscience]

Друзья, пишите под видео свои решения! Очень полезно и интересно их все читать!

[ИльяБондаренко-те]

Спасибо

function checkPath(start, end) {
const forbiddenCoordinates = {};

function isForbiddenCoordinates(y, x) {
return
}

function isAvailableCoordinates(level, x) {
return level?.[x] === 0;
}

function move(position) {
const {x, y} = position;

if (x === end.x && y === end.y) return true;
const level = maze[y];
const nextLevel = maze?.[y + 1];

const availableCoordinates = [];

if (isAvailableCoordinates(level, x - 1) && !isForbiddenCoordinates(y, x - 1)) availableCoordinates.push({x: x - 1, y});
if (isAvailableCoordinates(level, x + 1) && !isForbiddenCoordinates(y, x + 1)) availableCoordinates.push({x: x + 1, y});
if (isAvailableCoordinates(nextLevel, x) && !isForbiddenCoordinates(y + 1, x)) availableCoordinates.push({x: x, y: y + 1});

forbiddenCoordinates[y] ? : forbiddenCoordinates[y] = [x];

if (availableCoordinates.length === 0) {
return false;
}

for(let coordinate of availableCoordinates) {
if (move(coordinate)) return true;
}

return false;
}

return move(start);
}

[ВейсалТаштанов]

Обожаю решать ваши задачи. Некоторые из них заставляют сильно попотеть)

[denichi]

function checkPath(start, end) {
maze[start.y][start.x] = 5

const siblings = getValidSib(start);

if (siblings.length === 0) return false;

for (let i = 0; i < siblings.length; i++) {
const {x, y} = siblings[i];

const isSolved = y === end.y && x === end.x

if (isSolved || checkPath({x, y}, end)) return true;
}
}

function getValidSib(cord) {
const {x, y} = cord, cords = [];

if (maze[y - 1]?.[x] === 0) cords.push({x, y: y - 1});

if (maze[y + 1]?.[x] === 0) cords.push({x, y: y + 1});

if (maze[y][x - 1] === 0) cords.push({x: x - 1, y});

if (maze[y][x + 1] === 0) cords.push({x: x + 1, y});

return cords;
}

[edgarhovsepyan]

it's my solution .it's not the best but at least works



let maze = [
[1, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0],
];


function checkPath(start, end){

return false
}

return false
}

return false
}

return true;
}

maze[start.y][start.x]=2;

return checkPath({x:start.x+1, y:start.y}, { x: 5, y: 5 })||checkPath({x:start.x, y:start.y+1}, { x: 5, y: 5 })||
checkPath({x:start.x-1, y:start.y}, { x: 5, y: 5 })||checkPath({x:start.x, y:start.y-1}, { x: 5, y: 5 })
}

debugger;
console.log(checkPath({ x: 3, y: 0 }, { x: 5, y: 5 }));
console.log(maze);

[antiga]

function checkPath(start, end){
const n = maze.length - 1;
const {x, y} = start;
const moveTo = (x, y) => {
if (x < 0 || y < 0 || x > n || y > n || maze[y][x] !== 0) {
return false;
}

maze[y][x] = 5;

if (x === end.x && y === end.y) {
return true;
}

return moveTo(x - 1, y)
|| moveTo(x + 1, y)
|| moveTo(x, y - 1)
|| moveTo(x, y + 1);
}

return moveTo(x, y);
}

[ovocado]

1:08 - 5 минут назад ты сказал, что осталось 2 минуты.

[SerzhNesteruk]

Чуть заморочился над чистотой функции и иммутабельностью внешнего объекта maze. Вот, что получилось:

const checkPath = (entrance, exit, maze) => {
const map = Array.from(Array(maze.length), (_, y) => maze[y].map(v => v === 0));
map.isVisitable = function({x, y}) {
return this[y]?.hasOwnProperty(x) && this[y][x];
};
if (!map.isVisitable(entrance) || !map.isVisitable(exit)) {
return false;
}
(function traversing({x, y}, end, map) {
map[y][x] = false;
if (x === end.x && y === end.y) return;
const directions = [
{x: x + 1, y: y}, // right
{x: x, y: y + 1}, // down
{x: x - 1, y: y}, // left
{x: x, y: y - 1}, // up
];
for (const variant of directions) {
if (map.isVisitable(variant)) {
traversing(variant, end, map);
}
}
}(entrance, exit, map))
return !map[exit.y][exit.x];
};

[mikhailreznichenko]

Решения, пока своего нету ) Но видео классное!

[АлександрСердюков-жп]

Спасибо за задачу, минут 30 потратил и вот что получилось без рефакторинга
function maze(start, end) {
const lab = [
[1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 1],
[0, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0]
]

function step(pos) {
start.x = pos.x
start.y = pos.y

lab[pos.y][pos.x] = 2

const top = { x:pos.x, y:pos.y - 1 }
const left = { x:pos.x - 1, y:pos.y }
const right = { x:pos.x + 1, y:pos.y }
const bottom = { x:pos.x, y:pos.y + 1 }

if (lab[top.y] !== undefined && !lab[top.y][top.x])
step(top)

if (lab[left.y][left.x] !== undefined && !lab[left.y][left.x])
step(left)

if (lab[right.y][right.x] !== undefined && !lab[right.y][right.x])
step(right)

if (lab[bottom.y] !== undefined && !lab[bottom.y][bottom.x])
step(bottom)
}

step(start)

return (start.x === end.x && start.y === end.y)
}


console.log(maze({ x:3, y:0 }, { x:5, y:4 }))

[yarikmen]

Пробую на Java, не всегда срабатывает, где то логика у моего скрипта захромала. Если есть идеи как пофиксить, помогите. Спасибо.
Код:
import java.util.Arrays;

public class Maze {
public static void main(String[] args) {
// 1 приход
// 0 не проходной
// Вход [0, 0], выход [4, 4]


int[][] maze = {
{1, 0, 0, 0},
{1, 1, 0, 0},
{0, 1, 1, 1},
{1, 1, 1, 1}
};

int[][] maze1 = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{0, 1, 0, 1},
{1, 1, 1, 1}
};

int[][] grid = {
{1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
{1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

System.out.println(checkMaze(maze1, 0, 0, 4, 3));
->

System.out.println(checkMaze(maze, 0, 0, 3, 3));
->

System.out.println(checkMaze(grid, 0, 0, 12, 7));
->
}

private static boolean checkMaze(int[][] maze, int col, int row, int endCol, int endRow) {
maze[col][row] = 5;
if (col == endCol && row == endRow) {
return true;
}
boolean result = false;
// up
if (isValid(col, row - 1, maze) && maze[col][row - 1] != 5
|| (isValid(col, row - 2, maze) && maze[col][row - 1] == 5)
) {
row--;
result = checkMaze(maze, col, row, endCol, endRow);
}
// down
if (isValid(col, row + 1, maze) && !result && maze[col][row + 1] != 5
|| (isValid(col, row + 2, maze) && maze[col][row + 1] == 5)
) {
row++;
result = checkMaze(maze, col, row, endCol, endRow);
}
// left
if (isValid(col - 1, row, maze) && !result && maze[col - 1][row] != 5
|| (isValid(col, row, maze) && maze[col - 1][row] == 5)) {
col--;
result = checkMaze(maze, col, row, endCol, endRow);
}
// right
if (isValid(col + 1, row, maze) && !result && maze[col + 1][row] != 5
|| (isValid(col, row, maze) && maze[col + 1][row] == 5)) {
col++;
result = checkMaze(maze, col, row, endCol, endRow);
}
//System.out.println("col = " + col + " " + "row = " + row);
return result;
}

private static boolean isValid(int col, int row, int[][] maze) {
return col >= 0 && col < maze.length && row >= 0 && row < maze[0].length && maze[col][row] == 1;
}
}

[gamecenter]

Спасибо большое, но мой мозг сломалась🤯🤯

[a.osethkin]

Рекурсия - это весело, но лучше было бы использовать оценку расстояний (Дейкстры или в ширину вроде называется), тогда стек не надо забивать. #муравьиныйалгоритм

[sergeykhairulin]

Четыре if прям как то больно выглядят. Сделать бы массив ходов и пробегаться циклом по нему. И там же добавлять только 0 значения лабиринта, без фильтра.

[alexanderruzhik]

Возможно такой вариант является более простым для понимания или я неправильно понял условие? Но отрабатывает он как надо:
function checkPath(start, end) {

let {x, y} = start;

while (true) {
if (x === end.x && y === end.y) {
return true;
}
if (maze[y][x] === 0 && maze[y + 1][x] === 0) {
y++;
x = 0;
} else {
if (x === maze[0].length - 1) {
return false;
} else {
x++;
}
}
}
}

[antoncigur]

Самооценка[stonks]=‘dawn’
Вот скажите, только честно, как долго вы думали над алгоритмом ?

[olegm]

Спасибо за задачи! У меня вышло такое решение:
function checkPath(start, end) {
function step(x, y) {
// Если вышли за пределы
if (y < 0) return false;
if (y >= maze.length) return false;
if (maze[y][x] === undefined) return false;

// Если пошли по неверному пути
if (maze[y][x] === 1) return false;
if (maze[y][x] === 'x') return false;

if (x === end.x && y === end.y) return true;

maze[y][x] = 'x';

return step(x + 1, y) || step(x - 1, y) || step(x, y + 1) || step(x, y - 1);
}

return step(start.x, start.y);
}

[alumni]

В этот раз достаточно трудная задачка для меня, спасибо за ваши труды.
Вот мое решение. Сейчас буду смотреть ваше.

function checkPath(start, end) {
function canIgo(x, y) {
return x < 6 && x >= 0 && y < 6 && y >= 0 && maze[y][x] === 0
// определяем есть ли эта позиция и можно ли идти сюда
}


function step(x, y) {
if (x === end.x && y === end.y) return true; // если добрались в конец возвращаем true

const roads = []; // создаем массив возможных путей

if (canIgo(x + 1, y)) { //проверяем возможно ли перейти на все возможные позиции
roads.push([x + 1, y]);
}
if (canIgo(x - 1, y)) {
roads.push([x - 1, y]);
}
if (canIgo(x, y + 1)) {
roads.push([x, y + 1]);
}
if (canIgo(x, y - 1)) {
roads.push([x, y - 1]);
}

maze[y][x] = 9; // отмечаем 9-кой текущую позицию как пройденную


if (roads.length === 0) return false; // если идти больше некуда возвращаем false
// в зависимости от кол-ва доступных дорог проходим по ним всем
if (roads.length === 1) return step(roads[0][0], roads[0][1]);
if (roads.length === 2) return step(roads[0][0], roads[0][1]) ||
step(roads[1][0], roads[1][1]);
if (roads.length === 3) return step(roads[0][0], roads[0][1]) ||
step(roads[1][0], roads[1][1]) ||
step(roads[2][0], roads[2][1]);
}

return step(start.x, start.y);
}

console.log(checkPath({x : 3, y: 0}, {x: 5, y: 5}));

console.log(maze);

[ІльченкоАртем]

function road(arr, position = {x: 5, y: 0}, finish = {x: 5, y: 5}) {
try {
let array = [...arr]
let pos = {...position}
let fin = {...finish}
array[pos.y][pos.x] = 5


//Зачищаємо 9 шоб була видима тільки лінія правильного шляху
if (pos.x === fin.x && pos.y === pos.x) return array.map(el=>el.map(num=>{
if (num === 9) return 0
return num
}))


const left = {x: pos.x - 1, y: pos.y}
const right = {x: pos.x + 1, y: pos.y}
const up = {x: pos.x, y: pos.y - 1}
const down = {x: pos.x, y: pos.y + 1}

const objDirections = {
left, right, up, down
}
const objKeys = Object.keys(objDirections)

function isEmpty() {

for (let i = 0; i < objKeys.length; i++) {
if !== undefined
&& !== undefined
&& === 0) {
pos =
return true
}
}
array[pos.y][pos.x] = 9
//Коли впираємось в тупік повертаємось і йдемо назд по 5-кам пока не зустріним 0. Спочатку нас цікавить 0 а потім 5 шоб не піти назад

for (let i = 0; i < objKeys.length; i++) {
if !== undefined
&& !== undefined
&& === 5) {
pos =
return true
}
}
return false
}

if (isEmpty()) {
return road(array, pos, fin)
}
return array
} catch (err) {
return false
}
}