我使用了两个类:Cubicles 是那些有列和行号的六边形事物,以及 Paths 是 Cubicles 的有序列表。Cubicles 有一个函数分支来获取所有 Cubicles,它们在通往目的地的路径上的“正确方向”。只需一步即可从隔间直接到达。
然后我从长度为 1 的路径开始(仅开始),并通过所有分支稳步扩展这条路径,为每个分支生成一条路径,比旧的长 1。如果它不能再扩展,我们在 $dest 并且可以输出这个路径。
希望能帮助到你。花了一些时间来调试。让我知道它是否不适用于任何情况。
<?php
class Cubicle
{
public $col;
public $row;
public function branch(Cubicle $dest)
{
$result = array();
// move up
if ($this->row > $dest->row)
$result[] = new Cubicle($this->col, $this->row - 1);
// move down
elseif ($this->row < $dest->row)
$result[] = new Cubicle($this->col, $this->row + 1);
// move right
if ($this->col < $dest->col)
{
// right-up
if ($this->row >= $dest->row)
$result[] = new Cubicle($this->col + 1, $this->row);
// right-down
else
$result[] = new Cubicle($this->col + 1, $this->row - 1);
}
// move left
elseif ($this->col > $dest->col)
{
// left-up
if ($this->row > $dest->row)
$result[] = new Cubicle($this->col - 1, $this->row - 1);
// left-down
else
$result[] = new Cubicle($this->col - 1, $this->row);
}
return $result;
}
public function __construct($col, $row)
{
$this->col = $col;
$this->row = $row;
}
}
class Path
{
public $cubicles = array();
public function __construct(Cubicle $start)
{
$this->cubicles[] = $start;
}
public function getLast()
{
return $this->cubicles[count($this->cubicles)-1];
}
public function append($nextCubicle)
{
$clone = clone $this;
$clone->cubicles[] = $nextCubicle;
return $clone;
}
}
function walk(Cubicle $start, Cubicle $dest) {
$process = array(new Path($start));
$output = array();
while(count($process) > 0)
{
$currentPath = array_pop($process);
$branches = $currentPath->getLast()->branch($dest);
if (count($branches) == 0)
$output[] = $currentPath;
foreach ($branches as $branch)
$process[] = $currentPath->append($branch);
}
return $output;
}
$start = new Cubicle(4, 6);
$dest = new Cubicle(5, 5);
$paths = walk($start, $dest);
var_dump($paths);
?>
输出
array
0 =>
object(Path)[8]
public 'cubicles' =>
array
0 =>
object(Cubicle)[1]
public 'col' => int 4
public 'row' => int 6
1 =>
object(Cubicle)[5]
public 'col' => int 5
public 'row' => int 6
2 =>
object(Cubicle)[3]
public 'col' => int 5
public 'row' => int 5
1 =>
object(Path)[9]
public 'cubicles' =>
array
0 =>
object(Cubicle)[1]
public 'col' => int 4
public 'row' => int 6
1 =>
object(Cubicle)[4]
public 'col' => int 4
public 'row' => int 5
2 =>
object(Cubicle)[7]
public 'col' => int 5
public 'row' => int 5
这是一种非常低效的方法,因为如果您有重叠的路径,该算法将为每个路径重新计算这些路径的一部分。如果您想要一个性能良好的算法,您将需要创建某种图形,其中仅包含有效路径并深度优先搜索它以输出所有可能的路径。