当前位置:网站首页>PHP uses stack to solve maze problem
PHP uses stack to solve maze problem
2022-06-28 21:20:00 【liuliang514218119】
<?php
# Maze problem
# resolvent
#1. backtracking Start with a node , Find any point where you can walk , When you can't find a place to go , Go back to the previous point to find out if there is any other direction Use the stack to store the current path
$maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
];
function getDirection($x, $y)
{
$direction = [
[$x + 1, $y], # Next
[$x - 1, $y], # On
[$x, $y - 1], # Left
[$x, $y + 1] # Right
];
return $direction;
}
function maze_path($x, $y, $x1, $y1, $maze)
{
$stack = [];
array_push($stack, [$x, $y]); # Initialize the starting point
while (count($stack) > 0) {
# If the path is not empty
$cur_node = end($stack); # Current node
if ($cur_node[0] == $x1 && $cur_node[1] == $y1) {
# If the point of the path is the same as the end point, it means that there is a path
return $stack; # Return all paths in the stack
}
$diretion = getDirection($cur_node[0], $cur_node[1]); # Get the four directions of the current coordinate
$i = 0;
$pass = 0; # Is there a way
while ($i < 4) {
$next_node = $diretion[$i]; # Whether the four directions of the cycle can go
if ($maze[$next_node[0]][$next_node[1]] == 0) {
# If the next node can go Store the coordinates on the stack
array_push($stack, $next_node);
$maze[$next_node[0]][$next_node[1]] = 2; # Change the coordinates of the road to 2
$pass = 1; # There is a way
break;
}
$i++;
}
if (!$pass) {
# have no way out
/*print_r($next_node); echo "\n"; print_r($stack); echo "\n"; print_r($cur_node); exit;*/
$maze[$next_node[0]][$next_node[1]] = 2; # Change the coordinates of the road to 2
array_pop($stack); # If you can't go in all four directions Remove the coordinates from the stack
}
}
return False;
}
$res = maze_path(1, 1, 8, 8, $maze);
if ($res) {
echo ' There is a way ';
echo "\n";
print_r($res);
} else {
echo ' There is no way ';
}

边栏推荐
- Leetcode: expand a binary tree into a linked list_ one hundred and fourteen
- Application practice | 1billion data second level correlation. Huolala's OLAP System Evolution Based on Apache Doris (with PPT download)
- 请问同业存单是否靠谱,安全吗
- Is the inter-bank certificate of deposit reliable and safe
- 题解 Pie(POJ3122)超详细易懂的二分入门
- User network model and QoE
- Embedded dynamic Arabic string conversion LCD display string [thanks for Jianguo ambition]
- List of domestic database directory
- Alibaba cloud MSE full link grayscale solution practice based on Apache apisik
- 【激活函数】
猜你喜欢

API gateway Apache APIs IX helps the evolution of snowball dual active architecture

How do I download videos? Look at the super simple method!

MySQL system error occurred 1067

数据资产为王,如何解析企业数字化转型与数据资产管理的关系?
![[Note: circuit intégré MOS analogique] référence de bande Gap (principe de base + mode courant + circuit en mode tension)](/img/cd/be62272d465ca990456c222b38df67.png)
[Note: circuit intégré MOS analogique] référence de bande Gap (principe de base + mode courant + circuit en mode tension)

What is an interface? What is interface testing?
How to recover after Oracle delete accidentally deletes table data

如何使用 DataAnt 监控 Apache APISIX

Bitbucket 使用 SSH 拉取仓库失败的问题

Pyechart drawing multiple Y-axis line graphs
随机推荐
力扣树的进一步应用
Stability summary
postman简介与安装步骤
QT 一个控件的坐标怎么相对固定显示在另一个控件上(坐标系)
LeetCode560. 和为K的子数组
How to do a good job in customer's successful bottom design | tob Master Course
LeetCode122. 买卖股票的最佳时机II
Understanding of incomplete types
【读书会第13期】视频文件的封装格式
题解 Pie(POJ3122)超详细易懂的二分入门
关于不完全类型的认识
mysql-发生系统错误1067
[Note: analog MOS integrated circuit] bandgap reference (basic principle + current mode + voltage mode circuit explanation)
rapid ssl通配符证书八百一年是正版吗
LeetCode116. 填充每个节点的下一个右侧节点指针
ANR无响应介绍
Web automation tool selection
LeetCode56. 合并区间
LeetCode560. Subarray with and K
职场小技巧 | 了解岗位优势三板斧之“识人”