Skip to content

Решаем алгоритмическую задачу по нахождению пути в лабиринте

Notifications You must be signed in to change notification settings

aharitonov/find-path-in-maze

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

30 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

find-path-in-maze

Решаем алгоритмическую задачу по нахождению пути в лабиринте.

Лабиринт задается массивом из символов и имеет вид:

 1 _ _ _ _
 X X X X _
 _ E X _ _
 X _ _ X _
 _ _ _ _ _

1. Проверка существования пути

function pathExists(array $map, $startX, $startY, $exitX, $exitY): bool
{
    $m = new Map($map, $startX, $startY, $exitX, $exitY);

    echo vsprintf("Map condition: from [%d, %d] to [%d, %d]\n", array_merge(
        $m->getStart(),
        $m->getExit()
    ));
    echo $m->renderHumanizedView() . "\n";

    return (bool) Map::findPathToExit($m);
}

Смотри "path-exists.php"

2. Найти кратчайший путь

function findMinimalPath(array $map, $startX, $startY, $exitX, $exitY): ?array
{
    $m = new Map($map, $startX, $startY, $exitX, $exitY);
    $paths = Map::findPaths($m);

    $paths = array_filter($paths, static function (array $path) use ($m) {
        return end($path) === $m->getExit();
    });

    uasort($paths, static function (array $path1, array $path2) {
        return Map::calcPathLength($path1) - Map::calcPathLength($path2);
    });

    $index = array_key_first($paths);
    if ($index !== null) {
        return $paths[$index];
    }
    return null; // path not found
}

TODO

Смотри "find-path.php"

About

Решаем алгоритмическую задачу по нахождению пути в лабиринте

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages