Nadesłany przez foxbond, 18 marca 2013 09:45
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
skoczek.php:
<?php /** * Problem skoczka (konika) szachowego * @author Michał (Foxbond) Chraniuk [http://foxbond.cba.pl] * www.algorytm.org */ define('MEM_LIMIT', 2048); define('TIME_LIMIT', 30); @ignore_user_abort(false); @set_time_limit(TIME_LIMIT); @ini_set('memory_limit', MEM_LIMIT.'M'); /** * @return number */ function getmicrotime() { list($usec, $sec) = explode(" ",microtime()); return ((float)$usec + (float)$sec); } /** * @author Foxbond * */ class konik { /** * @var array */ protected $field = array(); /** * @var array */ protected $log = array(); /** * @var int */ protected $offsetX = 7; /** * @var int */ protected $offsetY = 7; /** * @var int */ protected $time = 0; /** * @var int */ protected $count = 0; /** * @var bool */ protected $writeLog = true; /** * @param int $sizeX * @param int $sizeY * @param bool $writeLog */ public function __construct ($sizeX=8, $sizeY=8, $writeLog=true){ $this->time = getmicrotime(); for($i=0;$i<$sizeY;$i++){ for($ii=0;$ii<$sizeX;$ii++){ $this->field[$i][$ii] = 0; } } $this->offsetX = $sizeX-1; $this->offsetY = $sizeY-1; $this->writeLog = $writeLog; } /** * @param int $x * @param int $y */ public function travel ($x, $y){ if($x < 0 || $y < 0){ return; } if ($x > $this->offsetX || $y > $this->offsetY){ return; } if ($this->field[$y][$x] == 1){ return; } $this->field[$y][$x] = 1; $this->logAddMove($x, $y); $this->count++; //gora $this->travel(($x-1), ($y-2)); $this->travel(($x+1), ($y-2)); //dol $this->travel(($x-1), ($y+2)); $this->travel(($x+1), ($y+2)); //prawo $this->travel(($x+2), ($y-1)); $this->travel(($x+2), ($y+1)); //lewo $this->travel(($x-2), ($y-1)); $this->travel(($x-2), ($y+1)); } /** * @return array:bool */ public function getEmptyFields (){ $e = array(); foreach ($this->field as $i => $v){ foreach ($v as $ii => $vv){ if ($vv == 0){ $e[] = array('x'=>$ii,'y'=>$i); } } } if (count($e) > 0){ return $e; } return false; } /** * @param int $x * @param int $y */ protected function logAddMove ($x, $y) { if ($this->writeLog){ $this->log[] = array('x'=>$x,'y'=>$y); } } /** * @param string $type */ public function showLog ($type='console'){ if ($type == 'console'){ echo 'Czas wykonywania skryptu: '.(getmicrotime()-$this->time).'s (max:'.ini_get('max_execution_time').'s)'."\r\n"; echo 'Użyta pamięć: '.round(((memory_get_usage(true)/1024)/1024), 2).'M (max:'.ini_get('memory_limit').')'."\r\n"; echo 'Liczba ruchów: '.$this->count."\r\n"; echo 'Zapis ruchów:'."\r\n"; foreach($this->log as $i => $v){ echo 'Skok na ['.$v['y'].','.$v['x']."]\r\n"; } $empty = $this->getEmptyFields(); if (!$empty){ echo 'Wszystkie pola odwiedzone!'; }else{ echo 'Nie udało się odwiedzić:'."\r\n"; foreach ($empty as $i => $v){ echo '('.$v['y'].','.$v['x'].')'; } } }else if ($type == 'consoleShort'){ echo 'Czas wykonywania skryptu: '.(getmicrotime()-$this->time).'s (max:'.ini_get('max_execution_time').'s)'."\r\n"; echo 'Użyta pamięć: '.round(((memory_get_usage(true)/1024)/1024), 2).'M (max:'.ini_get('memory_limit').')'."\r\n"; echo 'Liczba ruchów: '.$this->count."\r\n"; $empty = $this->getEmptyFields(); if (!$empty){ echo 'Wszystkie pola odwiedzone!'; }else{ echo 'Nie udało się odwiedzić:'."\r\n"; foreach ($empty as $i => $v){ echo '('.$v['y'].','.$v['x'].')'; } } } } } //skrypt zużywa o wiele więcej pamięci niż deklaruje //$konik = new konik(500, 500, false); $konik = new konik(10, 10); $konik->travel(0, 0); //$konik->showLog('consoleShort'); <- gdy rozwiązujemy problem dla dużej szachownicy $konik->showLog('console'); ?>