<?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');

?>