Advent of code 2019/15
Ajax Direct

Answer

[VISUALISATION] Part 1 :
Part 2 :
class BFSrobot extends Intcode
{
    public function __construct($program, $grid) {
        parent::__construct($program, []);
        $this->pos = xy([0, 0]);
        $this->nextPos = false;
        $this->grid = $grid;
    }

    /**
     * Plan the next move, register the next position
     *
     * @param int $input
     * @return self
     */
    public function addInput($input)
    {
        $this->input[] = $input;
        $this->direction = $input;

        $this->nextPos = (clone $this->pos)->direction(match ($input) {
            1 => "up",
            2 => "down",
            3 => "left",
            4 => "right"
        });

        return $input;
    }

    /**
     * Report the state, move the robot if not a wall and update the grid
     *
     * @param int $state
     * @return int The state
     */
    public function sendOutput($state)
    {
        if ($state) $this->pos = $this->nextPos;

        $this->grid->set($this->nextPos, match ($state) {
            0 => "#",
            1 => ".",
            2 => "!"
        });

        return parent::sendOutput($state);
    }

    /**
     * Clone the current robot for the BFS, shallow copy of its state
     *
     * @return void
     */
    public function __clone()
    {
        $this->input = clone $this->input;
        $this->output = clone $this->output;
    }
}

// ==================================================
// > PART 1 : BFS
// ==================================================
$bfs = new Graph(function ($graph) {
    $robot = $graph->robots[$graph->current];
    $next = [];

    foreach ([1, 2, 3, 4] as $dir) {
        $r = clone $robot;
        $r->addInput($dir);

        // If next pos already visited, abort
        if ($r->grid->get($r->nextPos)) continue;

        // Move robot, if not a wall then add to the bfs queue
        if ($r->run()) {
            $graph->robots[$graph->current . $dir] = $r;
            $next[$graph->current . $dir] = 1;
        }
    }

    return $next;
});

// Stop when we reached the oxygen stystem : status 2
$bfs->defineEnd(function ($graph) {
    return $graph->robots[$graph->current]->output->last() == 2;
});

// Track eveything in a grid
$grid = new Grid;
$grid->set([0, 0], "S");

// Explore from start position
$bfs->robots = new Set(["S" => new BFSrobot($input, $grid)]);
[$path_1, $solution_1] = $bfs->explore("S");

// ==================================================
// > PART 2 : DFS
// ==================================================

// First DFS : finish exploring the whole map
$dfs_1 = (clone $bfs)->setTarget("highest");
$dfs_1->queue = $bfs->queue;
$dfs_1->explore();

// Second DFS : find furthest point from oxygen
$dfs_2 = new Graph(function ($graph) use ($grid) {
    $current = xy(explode(";", $graph->current));
    $next = [];
    foreach ($current->getNeighbors() as $n) {
        $state = implode(";", $n);
        if (!isset($graph->values[$state]) && $grid->get($n) == ".") {
            $next[$state] = 1;
        }
    }
    return $next;
}, "highest");

$oxygen = (string) $bfs->robots[$bfs->current]->pos;
[$path_2, $solution_2] = $dfs_2->explore($oxygen);