The task is to find a path from the start point to the end point in a given 2D maze. The maze is represented as 2D array consisting of 0s and 1s, where 0 represents a path and 1 represents a wall. The start pointt and the end point are given. Write a function using DFS to check if there exists a path from the start point to the end point.
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = [0, 0]
end = [4, 4]
true (is path)
function dfs(grid, start, end){
const map = [
[-1, 0], //top
[1, 0], //bottom
[0, -1], //left
[0, 1], //right
];
const [startX, startY] = start;
let result = false;
if(
startX < 0 ||
startY < 0 ||
grid.length <= startX ||
grid[startX].length <= startY ||
grid[startX][startY] === '1'
){
return false;
}
grid[startX][startY] = '1';
if(startX === end[0] && startY === end[1]){
return true;
}
for(const [mx, my] of map){
const newX = startX + mx;
const newY = startY + my;
const answer = dfs(grid,[newX, newY], end);
if(answer){
result = answer;
}
}
return result;
}
function dfsRecursive(grid, start, end){
const stack = [start];
const directions = [
[-1, 0], //top
[1, 0], //bottom
[0, -1], //left
[0, 1], //right
]
while(stack.length > 0){
const [x, y] = stack.pop();
if(
x === end[0] && y === end[1]
){
return true;
}
if(
x < 0 ||
grid.length <= x ||
y < 0 ||
grid[x].length <= y ||
grid[x][y] === 1
){
continue;
}
grid[x][y] = 1;
console.log("=>(4.js:72) grid", grid);
console.log("=>(4.js:73) x,y", x,y);
for(const [mx, my] of directions){
stack.push([x+mx, y+my]);
}
}
return false;
}
function solution(grid, start, end){
const result = dfsRecursive(grid, start, end);
console.log("=>(4.js:39) result", result);
}
const maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
const start = [0, 0]
const end = [4, 4]
solution(maze, start, end);