如何找到网格上两个不同点之间的最短路线？

Question

我想制作一个函数来处理文本文件。

这个函数必须处理文本文件，然后找到最短的路径来实现点 1 到点 2。

示例：

* 1 - - - * * 
* * * * - - * 
* * - - - * -  
* * * * - * - 
2 - * * - * - 
* - - * - * -  
* * - - - - -

Answer 1

它可以优化，但我有几分钟的时间可以消磨，所以这就是我想出的。基本思路是逐行读取文件，然后分解space。遍历线条，然后标记每个点所在的字符。找出每个 X 和 Y 之间的差异，并根据这些差异生成一个字符串。输出是所采用的路径。

<?php 
//39883901.txt is the text file above
$File = fopen("39883901.txt", "r");
$Lines = array();
$PositionA = array();
$PositionB = array();
if($File) 
{
    while(($line = fgets($File)) !== false)
    {
        $Lines[] = explode(' ', $line);
    }

    fclose($File);
}
if(count($Lines) > 0)
{
    foreach($Lines as $y => $xvalues)
    {
        foreach($xvalues as $x => $value)
        {
            if($value == '1')
            {
                $PositionA['x'] = $x;
                $PositionA['y'] = $y;
            }
            if($value == '2')
            {
                $PositionB['x'] = $x;
                $PositionB['y'] = $y;
            }
        }
    }
    if(isset($PositionA['x'], $PositionA['y'], $PositionB['x'], $PositionB['y']))
    {
        $DifferenceX = $PositionB['x'] - $PositionA['x'];
        $DifferenceY = $PositionB['y'] - $PositionA['y'];
        $PadX = "R";
        $PadY = "D";
        if($DifferenceX < 0)
        {
            $PadX = "L";
            $DifferenceX = $DifferenceX * -1;
        }
        if($DifferenceY < 0)
        {
            $PadY = "U";
            $DifferenceY = $DifferenceY * -1;
        }
        $Travel = "";
        $Travel = str_repeat($PadX, $DifferenceX);
        $Travel .= str_repeat($PadY, $DifferenceY);

        echo "Travel Path: " . $Travel;
        //Travel Path: LDDDD
    }
}
?>

如何找到网格上两个不同点之间的最短路线？

How to find shortest route between two different points on a grid?

php

a-star