Backtracking method to solve maze problem

Introduction

I recently read some algorithm questions on leetcode. Some of them looked very simple and commonly used, but I couldn’t figure out how to solve them at once. For example: implementing the sqrt function, finding the arrangement of an 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 really wandering around. I can’t remember exactly where it is.

<code>1   1   1   1

0   1   0   1

0   1   0   1

0   1   1   1</code>

The top is a maze, the upper left corner is the entrance, and the lower right corner is the exit. Xiao Meng (yes, you read it right, it’s Xiao Ming with grass) enters from the entrance and escapes from the exit (can’t escape in 1 hour) Will be eaten by monster

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 take a look at the definition of the backtracking method (Baidu Encyclopedia):

The backtracking method (exploration and backtracking method) is a method of optimal search, and It is called heuristic method and searches forward according to the optimal 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:

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

Look at my PHP implementation:

<code><?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";
}

//输出结果
(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</code>

The above introduces the backtracking method to solve the maze problem, including the relevant aspects. I hope it will be helpful to friends who are interested in PHP tutorials.