Maze problem
We’re often faced with the maze problem of how to get from the beginning to the end:
Or find the shortest path from start to finish:
For this kind of maze problem, we use the idea of programming, which can be simply abstracted into a two-dimensional array matrix of M*N, as follows:
var matrix =
[[0.1.0.0.0.0]
[0.1.0.1.0.0]
[0.0.0.0.0.1]
[1.1.0.0.0.0]
[1.1.0.0.0.0]
[1.1.0.0.0.0]]
Copy the codeIn the above two-dimensional array, take the upper left corner as the starting point and the lower right corner as the end point. Each point has four directions that can be taken up, down, and left. 0 indicates that the path can be passed, and 1 indicates that the obstacle cannot be passed.
In one of the ways shown below, we use “#” to represent the path:
We can easily find a way, of course, this is only for the matrix is small, if the matrix is large enough, then we need to convert into a programming language to solve the problem.
Depth-first search
Depth-first search, also known as depth-first traversal, is a common search method. Its characteristic is to go deep without hitting the south wall and never turning back. The depth-first maze traversal process is as follows:
- Access the starting point s.
- Starting from the unvisited adjacent points of S in turn, search is conducted in a certain direction until the search in this direction is completed and all points that have path communication with S are accessed.
- If there are still unvisited nodes, start from one unvisited node and conduct in-depth search again until all nodes are accessed.
- Repeat the above operations until the access ends at e.
While searching, we need to add some judgment conditions to avoid some illegal path states,
- The current node is a path.
- The current node does not exceed the maze range.
- The current node should not be accessed twice in the same path.
Finally, it is necessary to record the path visited during the search. According to the above ideas, it is converted into JavaScript code and implemented recursively:
var mazeSearch = function(){
var matrix =
[[0.1.0.0.0.0],
[0.0.0.1.0.0],
[0.0.1.0.0.1],
[1.1.0.0.0.0],
[1.1.0.0.0.0],
[1.1.0.0.0.0]]
var m = matrix.length
var n = matrix[0].length
// This array is used to record whether the current node has been accessed
var visited = new Array(m).fill(' ').map((d) = >new Array(n).fill(false))
var dirs = [[0.1], [0, -1], [1.0], [...1.0]] // The current node can go in four directions: right, left, up, and down
var dfs = function(x,y,path){
// get to the end
if (x == m-1 && y == n-1) {
console.log(path) // Prints the current path
return
}
for (var dir of dirs) {
var nx = x + dir[0]
var ny = y + dir[1]
// Check whether the current node is valid
if (nx < m && // The maze boundary
nx >=0 &&
ny < n &&
ny >=0 &&
matrix[nx][ny] == 0 && // Whether Pathway 0: pathway 1: obstacle
visited[nx][ny] == false) {// Whether it has been accessed
// When the node is accessed, it is marked as accessed
visited[nx][ny] = true
// Enter recursion, each recursion represents a complete path
// You need to pass in the current node and the path already accessed
dfs(nx,ny,path+The '-'+nx+', '+ny)
// Each time the path completes, the original state needs to be traced for that node
visited[nx][ny] = false; }}}// Enter the starting point
dfs(0.0.'0, 0')
visited[0] [0] = true
}
Copy the codeThe above code prints out all the paths from the beginning to the end. Finally, we can draw the paths of some of the 212 solutions at random, as shown below:
The number above each path represents the length of the current path, that is, the number of nodes it has traversed. As you can see, different paths have different lengths. So, can we find the shortest path among the 212 paths?
var mazeSearch = function(){...var res = {
path:null.len:Number.MAX_SAFE_INTEGER
}
var dfs = function(x,y,path){
// get to the end
if (x == m-1 && y == n-1) {
// Get the current path length
var currentLen = path.split(The '-').length
// If the current path is smaller than the result path, the result path is taken
if (res.len > currentLen) {
res = {
path:path,
len:currentLen
}
}
return}... }...console.log(res)
}
Copy the codePrint out the optimal solution with the length of 12:
{
len: 13,
path: "0, 1, 0, 0-1-1-1, 2, 2, 3-0 0 0, 4-1, 4-2, 4-3, 4, 3, 5-4, 5-5, 5"
}
Copy the codeThe core idea is to get the optimal solution through depth-first search, and then find the optimal solution from all the solutions. So can we take a more efficient way to get the optimal solution directly?
Breadth-first search
Breadth-first search, also known as breadth-first traversal, is a common search method that is characterized by a point that spreads out in all directions, that is, in a manner of divergence, and so on, until all vertices are searched. The idea is the evolution of sequential traversal of binary trees, traversal layer by layer.
Breadth-first search is usually used to find the optimal solution, that is, when the result is obtained, the result is the shortest path. In breadth-first traversal, the related points around nodes that have not been traversed will be traversed first, and then this step will be repeated until all nodes have been traversed. Since there are multiple nodes associated with a node that cannot be traversed at the same time, we need to use the data structure queue to simulate such “simultaneous” traversal. The process and idea are as follows:
- Access the starting point s.
- Take the starting point as the current node, traverse all four directions of the point, press it into the queue, and mark it as visited.
- Remove the node with the first node in the current direction from the queue and record the path.
- Repeat steps 2,3 above until you reach destination e.
Also, while searching, we need to add some judgment criteria to avoid some illegal path states,
- The current node is a path.
- The current node does not exceed the maze range.
- The current node should not be accessed twice in the same path.
Convert to JavaScript code along the lines above:
var mazeSearch = function(){
var matrix =
[[0.1.0.0.0.0],
[0.0.0.1.0.0],
[0.0.1.0.0.1],
[1.1.0.0.0.0],
[1.1.0.0.0.0],
[1.1.0.0.0.0]]
var m = matrix.length
var n = matrix[0].length
// This array is used to record whether the current node has been accessed
var visited = new Array(m).fill(' ').map((d) = >new Array(n).fill(false))
var arr = [] / / the queue
var dirs = [[0.1], [0, -1], [1.0], [...1.0]]// The current node can go in four directions: right, left, up, and down
// Start to join the team
arr.push({
x:0.y:0.path: '0, 0'
})
visited[0] [0] = true
while(arr.length) {
var current = arr.shift() // The node in the current direction is queued
if (current.x == m-1 && current.y == n-1) {
console.log(current.path)// Prints the current path
break;
}
for (var dir of dirs) {
var nx = current.x + dir[0]
var ny = current.y + dir[1]
// Check whether the current node is valid
if (nx < m && // The maze boundary
nx >=0 &&
ny < n &&
ny >=0 &&
matrix[nx][ny] == 0 && // Whether Pathway 0: pathway 1: obstacle
visited[nx][ny] == false) {// Whether it has been accessed
// Records the path traveled according to the current path
var _path = current.path + The '-'+nx+', '+ny+' '
// The node joins the queue
arr.push({
x:nx,
y:ny,
path:_path
})
// The flag has been accessed
visited[nx][ny] = true}}}}Copy the codeSo far, we have used breadth first search and depth first search respectively to complete the maze problem, of course, this is only the simplest maze problem, there are many similar variations.
Variant of labyrinth problem
- The direction of increasing
For example, each point has 8 directions to move, we can modify the directions array by:
Var dirs = [[0, 1], [0, 1], [1, 0], [- 1, 0], [1, 1], [1, 1], [1, 1], [1, 1]] / / respectively corresponding to the right, left, on, under, top right, bottom left, right, top leftCopy the code- Ball rolling topic:
In the maze there is a ball with empty Spaces and walls. The ball can move by rolling up, down, left or right, but it does not stop rolling until it hits the wall. When the ball stops, it can choose the next direction and find the shortest path for the ball from start to finish.
The biggest difference in this problem is that the ball will not stop when it meets an obstacle, but can move in four directions until it meets the wall. Therefore, we have sorted out two changes based on the above ideas:
- The wall, the boundary of the maze is judged separately.
- will
ifInstead ofwhileThat is, the loop determines whether it is a valid path.
The code is as follows:
shortestDistance(maze,start,destination) {
var m = maze.length
var n = maze[0].length
var res = Number.MAX_SAFE_INTEGER
var visited = new Array(m).fill(' ').map(d= >new Array(n).fill(false))
var dirs = [[-1.0], [1.0], [0, -1], [0.1]].// Pull away from the wall maze boundary
var notWall = function(x,y){
return x >= 0 && x < m && y >= 0 && y < n;
}
var dfs = function(x,y,step){
if(x == destination[0] && y == destination[1]) {
res = Math.min(res,step)
return
}
for(var dir of dirs) {
var nx = x, ny = y;
var _step = step
// make a loop judgment
while(notWall(nx + dir[0], ny + dir[1]) && maze[nx+dir[0]][ny+dir[1]] != 1) {
nx += dir[0];
ny += dir[1];
_step = _step+1
}
if(! visited[nx][ny]) { visited[nx][ny] =true
dfs(nx,ny,_step)
visited[nx][ny] = false
}
}
}
dfs(start[0],start[1].0)
return res == Number.MAX_SAFE_INTEGER ? -1 : res
}
Copy the code- Other topics
For example, adding random portals to mazes, LeetCode 200. Island count, LeetCode 695. The topics such as the maximum area of the island are all variations of the maze problem, and the core idea is to use depth first and breadth first search to solve it.
Other articles:
Front algorithm: binary tree traversal front algorithm: palindrome string