Как найти кратчайший маршрут между двумя разными точками на сетке?

Question

Как найти кратчайший маршрут между двумя разными точками на сетке?

Я хотел бы сделать функцию для обработки текстового файла.

Эта функция должна обработать текстовый файл и затем найти кратчайший путь для достижения точки 1 — точки 2.

Пример:

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

-2

a-star php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это можно было оптимизировать, но у меня было несколько минут, чтобы убить, так что вот что я придумал. Основная идея состоит в том, чтобы прочитать файл построчно, а затем разбить его на место. Перебирайте строки, затем символы, отмечающие, где находится каждая точка. Найдите разницу между каждым 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
}
}
?>

2