Detailed explanation of PHP using backtracking method to solve maze problem

This article mainly introduces the PHP method to solve the maze problem based on the backtracking method. It analyzes the principle of the backtracking method in detail, the implementation steps and the related operating skills for solving the maze problem in the form of examples. Friends in need can refer to the following

The example in this article describes how PHP implements the method of solving the maze problem based on the backtracking method. I share it with you for your reference. The details are as follows:

Introduction

I recently read some algorithm questions on leetcode, and some of them looked very simple. There are very commonly used things, but I can't figure out how to solve them at once, such as: implementing the sqrt function and finding the arrangement of the array. If you are not good at advanced mathematics, these seemingly simple problems will be difficult to solve for the first time you encounter them. Of course, what we are going to talk about today is such a problem, how to solve all the solutions to the maze. How to solve this problem When it comes to the idea of ​​backtracking, if you don't understand this idea, many slightly more complicated problems will be difficult to solve.

Problem Description

I encountered this problem when I was just wandering around. I can’t remember exactly where it was.

1 1 1 1
0 1 0 1
0 1 0 1
0 1 1 1

The top is a maze, the upper left corner is the entrance, and the lower right corner is At the exit, Xiaomeng (yes, you read it right, it’s Xiao Ming who has grown grass) enters from the entrance and escapes from the exit (if you can’t escape for an hour, you will be eaten by the X monster), where 1 means it can pass, and 0 means There is no way to pass, so you can only go in two directions: right and down. Find all the possible escape routes for Xiaomeng.

This question seems quite simple, and you can see the answer at once, but I don’t know where to start when translating thoughts into code.

How to solve

One solution to this problem is the backtracking method. Let’s first look at the definition of the backtracking method (Baidu Encyclopedia):

The backtracking method (exploration and backtracking method) is a optimization search method, also known as the heuristic method, which searches forward according to the optimization conditions to achieve the goal. But when you reach a certain step in exploration and find that the original choice is not optimal or cannot achieve the goal, you will take a step back and make another choice. This technique of going back and trying again when it doesn't work is the backtracking method, and the point in a certain state that satisfies the backtracking conditions Called the "lookback point".

My idea:

1. Coordinate the maze above, the upper left corner is (0,0), the lower right corner is (3,3), Other points are scattered in the coordinate system
2. Start from (0,0)
3. Start from the given coordinate point, search to the right first, if it is 1, continue, if it is 0, search downward, search Record the coordinates that have been searched before
4. When the coordinates are equal to (3,3), it is a backtracking point. At this time, it also returns
5. As long as it does not cross the boundary, repeat the third step

Look at my PHP implementation:

<?php
$nums = [
  [1,1,1,1,1,1],
  [0,1,0,1,0,1],
  [0,1,0,1,0,1],
  [0,1,1,1,1,1]
];
function getRet($data, $x, $y, &$result=[], $record)
{
  $snapshort = [];
  $xL = count($data) - 1;
  $yL = count($data[0]) - 1;
  if($x > $xL || $y > $yL) {
    //跑到迷宫不存在的空间了，这种事情绝对不能发生
    return;
  }
  if($data[$x][$y] == "0") {
    //是0的话停止继续前进，退回上一状态
    return;
  } elseif($data[$x][$y] == "1") {
    //是1的话，记录最新的坐标到当前已找到的路径中，继续向前搜索
    //如果到达出口，记录答案并回溯
    $snapshort = array_merge($record, [[$x, $y]]);
    if($x == $xL && $y == $yL) {
      $result[] = array_merge($record, [[$x, $y]]);
      return;
    }
  } else {
    return;
  }
  //向有搜索
  //这里的$snapshort保存当前搜索位置的状态，等到下次回溯到这里的时候会用到
  getRet($data, $x, ++$y, $result, $snapshort);
  //向下搜索
  getRet($data, ++$x, --$y, $result, $snapshort);
}
//看个例子
$result = [];
getRet($nums, 0, 0, $result, []);
foreach ($result as $pos) {
  foreach ($pos as $xy) {
    echo "({$xy[0]},{$xy[1]}) => ";
  }
  echo "end\n";
}

Output result

(0,0)=>(0,1)=>(0,2)=>(0,3)=>(0,4)=>(0,5)=>(1,5)=>(2,5)=>(3,5)=>end
(0,0)=>(0,1)=>(0,2)=>(0,3)=>(1,3)=>(2,3)=>(3,3)=>(3,4)=>(3,5)=>end
(0,0)=>(0,1)=>(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)=>(3,4)=>(3,5)=>end

The above is the detailed content of Detailed explanation of PHP using backtracking method to solve maze problem. For more information, please follow other related articles on the PHP Chinese website!