cost = $cost; $this->previous = $previous; $this->move = $move; } public function getCost(){ return $this->cost; } public function getMove(){ return $this->move; } public function getPrevious(){ return $this->previous; } } class Graph { private $n; private $graph = null; private $move = array( 'LL' => [2,-1], 'L' => [0, -2], 'UL' => [-2, -1], 'LR' => [2, 1], 'R' => [0, 2], 'UR' => [-2, 1] ); public function printShortestPath($n, $i_start, $j_start, $i_end, $j_end) { // Print the distance along with the sequence of moves. $this->n = $n; $this->setGraph($i_start,$j_start,0); $this->generatePath($i_start,$j_start,0); //print_r($this->graph); if(!isset($this->graph[$i_end][$j_end])||$this->graph[$i_end][$j_end]->getMove()==""){ echo "Impossible"; } else { echo $this->graph[$i_end][$j_end]->getCost() . "\n"; $this->printPath($i_end, $j_end); } } private function generatePath($i, $j, $cost, $depth = 0){ if($depth>$this->n/2) return; $moves = $this->getMove($i, $j, $cost); foreach($moves as $k=>$m){ $this->setGraph($m[0],$m[1],$cost+1,$k,array($i, $j)); $this->generatePath($m[0],$m[1],$cost+1, $depth+1); } } private function printPath($i,$j){ if(isset($this->graph[$i][$j])&&$this->graph[$i][$j]->getMove()!=""){ list($m,$n) = $this->graph[$i][$j]->getPrevious(); $this->printPath($m,$n); echo $this->graph[$i][$j]->getMove() . " "; } } private function getCost($i,$j){ if(isset($this->graph[$i][$j])) return $this->graph[$i][$j]->getCost(); else return 1000; } private function setGraph($i,$j,$cost,$move='',$previous=array()){ $this->graph[$i][$j] = new Vertice($cost,$move,$previous); } private function getMove($i, $j, $cost){ $move_list = array(); foreach($this->move as $key=>$m){ $im = $i+$m[0]; $jm = $j+$m[1]; if($im>=0&&$jm>=0&&$im<$this->n&&$jm<$this->n&&$this->getCost($im,$jm)>$cost) $move_list[$key] = array($im,$jm); } return $move_list; } } fscanf($handle, "%i",$n); fscanf($handle, "%i %i %i %i", $i_start, $j_start, $i_end, $j_end); (new Graph())->printShortestPath($n, $i_start, $j_start, $i_end, $j_end); ?>