google task

<?php

class Google {
    private $_input;
    private $_output;

    public function __construct($input)
    {
        $this->_input = $this->_output = $input;
    }

    public function solve(){
        for($i = 0; $i < sizeof($this->_input); $i++){
            for($j = 0; $j < sizeof($this->_input[$i]); $j++){
                $this->_output[$i][$j] =
                    $this->_input[$i][$j] === 0
                        ? $this->step($i, $j)
                        : $this->_input[$i][$j];
            }
        }
        return $this;
    }

    public function result(){
        return $this->_output;
    }

    protected function step($i, $j, $path = array(), &$results = array()){
        $path[] = $this->coordinate($i, $j);

        if($this->_input[$i][$j] === 'G'){
            return sizeof($path) - 1;
        }
        if($this->_input[$i][$j] === 'B'){
            return INF;
        }

        if($this->check($i, $j + 1, $path)){
            $results[] = $this->step($i, $j + 1, $path);
        }
        if($this->check($i, $j - 1, $path)){
            $results[] = $this->step($i, $j - 1, $path);
        }
        if($this->check($i + 1, $j, $path)){
            $results[] = $this->step($i + 1, $j, $path);
        }
        if($this->check($i - 1, $j, $path)){
            $results[] = $this->step($i - 1, $j, $path);
        }

        return min($results);
    }

    protected function coordinate($i, $j){
        return $i * sizeof($this->_input[$i]) + $j;
    }

    protected function check($i, $j, $path){
        return isset($this->_input[$i][$j]) && array_search($this->coordinate($i, $j), $path) === false;
    }
}

$input = array(
    array( 0,   0,   0 ),
    array('B', 'G', 'G'),
    array('B',  0,   0 ),
);

$google = new Google($input);
$result = $google->solve()->result();

echo "<table border='1' cellspacing='0' cellpadding='5' style='margin-bottom: 20px;'>";
foreach($result as $row){
    echo "<tr><td>" . implode("</td><td>", $row) . "</td></tr>";
}
echo "</table>";