1, 'UR' => 2, 'R' => 3, 'LR' => 4, 'LL' => 5, 'L' => 6]; function newElement($x, $y, $k, $p, $n) { $el = new StdClass(); $el->x = $x; $el->y = $y; $el->k = $k; $el->p = $p; return $el; } function pushArr($x, $y, $k, $p, $n) { if ($x >= 0 && $x < $n && $y >=0 && $y < $n && !in_array($x.','.$y, $GLOBALS['VISIT'])) { $el = newElement($x, $y, $k, $p, $n); array_push($GLOBALS['ARRAY'], $el); } } function appendArr($element, $n) { $x = $element->x; $y = $element->y; $k = $element->k + 1; $p = $element->p; pushArr($x, $y + 2, $k, $p . ' R', $n); pushArr($x + 2, $y + 1, $k, $p . ' LR', $n); pushArr($x + 2, $y - 1, $k, $p . ' LL', $n); pushArr($x, $y - 2, $k, $p . ' L', $n); pushArr($x - 2, $y - 1, $k, $p . ' UL', $n); pushArr($x - 2, $y + 1, $k, $p . ' UR', $n); } function printShortestPath($n, $i_start, $j_start, $i_end, $j_end) { // Print the distance along with the sequence of moves. pushArr($i_start, $j_start, 0, '', $n); while (sizeof($GLOBALS['ARRAY']) > 0) { $element = array_shift($GLOBALS['ARRAY']); array_push($GLOBALS['VISIT'], $element->x .','. $element->y); if ($element->x == $i_end && $element->y == $j_end) { return $element; } appendArr($element, $n); } return false; } function printEL($p) { $p = trim($p); $ar = explode(" ", $p); for ($i = 0; $i < sizeof($ar); $i++) { for ($j = 0; $j < sizeof($ar); $j++) { if ($GLOBALS['SORT'][$ar[$i]] <= $GLOBALS['SORT'][$ar[$j]]) { $tmp = $ar[$i]; $ar[$i] = $ar[$j]; $ar[$j] = $tmp; } } } return implode(' ', $ar); } fscanf($handle, "%i",$n); fscanf($handle, "%i %i %i %i", $i_start, $j_start, $i_end, $j_end); $result = printShortestPath($n, $i_start, $j_start, $i_end, $j_end); if (!$result) { echo "Impossible"; } else { print $result->k . "\n"; print trim(printEL($result->p)); } ?>