当前位置:网站首页>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 ';
}

边栏推荐
- Learning Tai Chi Maker - mqtt Chapter II (VII) esp8266 mqtt Testament application
- 题解 Andy s First Dictionary(UVa10815)紫书P112set的应用
- 图神经网络也能用作CV骨干模型,华为诺亚ViG架构媲美CNN、Transformer
- LeetCode:合并两个有序链表_21
- How to recover after Oracle delete accidentally deletes table data
- Web自动化工具选择
- Ehcache configuration data, convenient for self checking
- Building web automation environment
- QT how the coordinates of one control are relatively fixed and displayed on another control (coordinate system)
- rapid ssl通配符证书八百一年是正版吗
猜你喜欢

Ref attribute, props configuration, mixin mixing, plug-in, scoped style

Alibaba cloud MSE full link grayscale solution practice based on Apache apisik

LeetCode每日一题——515. 在每个树行中找最大值

力扣树的进一步应用

Pyechart drawing multiple Y-axis line graphs
![[Note: analog MOS integrated circuit] bandgap reference (basic principle + current mode + voltage mode circuit explanation)](/img/cd/be62272d465ca990456c222b38df67.png)
[Note: analog MOS integrated circuit] bandgap reference (basic principle + current mode + voltage mode circuit explanation)

什么是接口?什么是接口测试?

with torch. no_ Grad(): reason for using

What is an interface? What is interface testing?

mysql-发生系统错误1067
随机推荐
Apisik helps Middle East social software realize localized deployment
Pie (poj3122) super detailed and easy to understand binary introduction
QT how the coordinates of one control are relatively fixed and displayed on another control (coordinate system)
【筆記:模擬MOS集成電路】帶隙基准(基本原理+電流模+電壓模電路詳解)
mysql-发生系统错误1067
【激活函数】
Application practice | 1billion data second level correlation. Huolala's OLAP System Evolution Based on Apache Doris (with PPT download)
如何添加 logs来debug ANR 问题
题解 Pie(POJ3122)超详细易懂的二分入门
LeetCode122. 买卖股票的最佳时机II
Leetcode daily question - 324 Swing sort II
LeetCode1114. Print in sequence
LeetCode每日一题——324. 摆动排序 II
Résumé de la stabilité
Ref attribute, props configuration, mixin mixing, plug-in, scoped style
How do I download videos? Look at the super simple method!
API 网关 Apache APISIX 助力雪球双活架构演进
MongoDB——副本集与分片
LeetCode226. Flip binary tree
Postman introduction and installation steps