Code

gistfile1.txt

class System
{
    const MAX_LENGTH = 8;
    const MAX_STEP_TO = 2;
    static public $a = [];
    static public $start = [];
    static public $dest = [];
    static public $maxX = 0;
    static public $maxY = 0;
    static public $result = 0;
    static public $isFinished = false;
}
function directions()
{
    return ['L', 'R', 'U', 'D'];
}
function labyrinthNavigation($labyrinth, $start, $dest) {
    foreach ($labyrinth as $i => $str) {
        System::$a[$i] = [];
        foreach (str_split($str) as $j => $row) {
            System::$a[$i][$j] = $row == '.' ? 0 : -1;
        }
    }
    System::$start = $start;
    System::$dest = $dest;
    System::$maxX = count(System::$a) - 1;
    System::$maxY = count(System::$a[0]) - 1;
    for ($i = 1; $i <= System::MAX_LENGTH; $i++) {
        generateSequence(1, $i, []);
    }
    return System::$result;
}

function generateSequence($i, $length, $s)
{
    if (System::$isFinished) {
        return true;
    }
    foreach (['L', 'R', 'U', 'D'] as $d) {
        $s[$i] = $d;
        if ($i < $length) {
            generateSequence($i + 1, $length, $s);
        } else {
            $result = applySequence($s, System::$a, System::$start, System::$dest);
            if (is_int($result)) {
                System::$isFinished = true;
                System::$result = $result;
            }
        }
    }
    return false;
}

function applySequence($sequence, $a, $current, $dest)
{
//    echo sprintf('Start sequencing for %s', implode($sequence, '-')) . PHP_EOL;
    $b = $a;
    while ($result = applyOneSequence($sequence, $b, $current, $dest)) {
        if ($result === true) {
            echo sprintf('Found sequence: %s', implode($sequence, '-')) . PHP_EOL;
            return count($sequence);
        }
        if ($result === false) {
            return false;
        }
        if (is_array($result)) {
            $current = $result;
        }
    }
    return false;
}
function applyOneSequence($sequence, &$a, $current, $dest)
{
    $x = $current[0]; $y = $current[1];
    $a[$x][$y]++;
    if ($a[$x][$y] > System::MAX_STEP_TO) {
        return false;
    }
//    echo sprintf('Stepping to [%s, %s]', $x, $y) . PHP_EOL;
    if ($x == $dest[0] && $y == $dest[1]) {
        return true;
    }
    if (empty($sequence)) {
        return $current;
    }
    $currentStep = array_shift($sequence);
    switch ($currentStep) {
        case 'U':
            if ($x == 0 || $a[$x - 1][$y] == -1) {
                return false;
            } else {
                return applyOneSequence($sequence, $a, [$x - 1, $y], $dest);
            }
            break;
        case 'D':
            if ($x >= System::$maxX || $a[$x + 1][$y] == -1) {
                return false;
            } else {
                return applyOneSequence($sequence, $a, [$x + 1, $y], $dest);
            }
            break;
        case 'L':
            if ($y == 0 || $a[$x][$y - 1] == -1) {
                return false;
            } else {
                return applyOneSequence($sequence, $a, [$x, $y - 1], $dest);
            }
            break;
        case 'R':
            if ($y >= System::$maxY || $a[$x][$y + 1] == -1) {
                return false;
            } else {
                return applyOneSequence($sequence, $a, [$x, $y + 1], $dest);
            }
            break;
    }
    return false;
}

$t = labyrinthNavigation(
    [".........**....",
        ".*...*...*.**..",
        ".**............",
        "......*...*...."],
    [1, 3],
    [3, 14]
);
var_dump($t);