<?php

error_reporting(1);
mb_internal_encoding("utf-8");


class Field
{
    private $animals = [];
	private $fieldSchema;
	private $fieldSize;
	
	public function __construct($fieldSize)
	{
	    $this->fieldSize = $fieldSize;
	}
	
	public function drawFieldSchema()
	{
	    for($i = 1; $i <= pow($this->fieldSize, 2); $i++) {
            $this->fieldSchema[$i] = ". ";
        }    
	}
	
	public function addAnimal(Animal $animal) 
	{
	    $this->animals[] = $animal;
	}
	
	public function removeAnimal(Animal $animal)
	{
	    $key = array_search($animal, $this->animals, true);
	    unset($this->animals[$key]);
	}
	
	public function drawAnimals()
	{ 
	    foreach($this->animals as $animal) {
		    if(get_class($animal) === "Mouse") {
			    $this->fieldSchema[$animal->getPosition()] = "M ";
			} else if(get_class($animal) === "Cat") {
			    if($animal->isSleepy()) {
				    $this->fieldSchema[$animal->getPosition()] = "@ ";
				} else {
			        $this->fieldSchema[$animal->getPosition()] = "K ";
				}
			} else {
			    $this->fieldSchema[$animal->getPosition()] = "C ";
			}
		}
	}
	
	public function concatenateToShema($info, $line)
	{
	    $this->fieldSchema[$line * $this->fieldSize] .= $info;
	}
	
	public function __toString()
	{
	    $fieldSchemaLined = [];
		$chunkedField = array_chunk($this->fieldSchema, $this->fieldSize, true);
		foreach($chunkedField as $chunk) {
		    $fieldSchemaLined = array_merge($fieldSchemaLined, $chunk);
			$fieldSchemaLined[] = "\n";
		}
		return implode("", $fieldSchemaLined);
	}
}


abstract class Animal
{
    protected $position;
	protected $fieldSize;
	
	public function __construct($fieldSize)
	{
	    $this->fieldSize = $fieldSize;
	}
	
	public function getPosition()
	{
	    return $this->position;
	}
	
	public function setPosition($position) 
	{
	    $this->position = $position;
	}
	
	protected function findOrthogonalSteps()
	{
	    $orthSteps = [];
	    if($this->position > $this->fieldSize) {	
	        $orthSteps[] = $this->position - $this->fieldSize;
		}
		if($this->position % $this->fieldSize !== 0) {
		    $orthSteps[] = $this->position + 1;
		}
		if(pow($this->fieldSize, 2) - $this->position >= $this->fieldSize) {
		    $orthSteps[] = $this->position + $this->fieldSize;
		}	
		if(($this->position - 1) % $this->fieldSize !== 0) {
		    $orthSteps[] = $this->position - 1;
		}
		return $orthSteps;
	}
	
	protected function findDiagonalSteps()
	{
	    $diagonalSteps = [];
		if($this->position > $this->fieldSize && $this->position % $this->fieldSize !== 0) {
           	$diagonalSteps[] = $this->position - $this->fieldSize + 1;
		}
		if($this->position > $this->fieldSize && ($this->position - 1) % $this->fieldSize !== 0) {	
		    $diagonalSteps[] = $this->position - $this->fieldSize - 1;
		}
		if(pow($this->fieldSize, 2) - $this->position >= $this->fieldSize && 
		   $this->position % $this->fieldSize !== 0) {
            $diagonalSteps[] = $this->position + $this->fieldSize + 1;
		}
		if(pow($this->fieldSize, 2) - $this->position >= $this->fieldSize && 
		   ($this->position - 1) % $this->fieldSize !== 0) {
            $diagonalSteps[] = $this->position + $this->fieldSize - 1;
		}
		return $diagonalSteps;
	}	
	
	protected function excludeClosedPositions(array $animals, array $availableSteps)
	{
	    $animalsPositions = [];
		foreach($animals as $animal) {
		    $animalsPositions[] = $animal->getPosition();
		}
	    $closedPositions = array_intersect($animalsPositions, $availableSteps);
		if($closedPositions) {
		    foreach($closedPositions as $closed) {
			    $key = array_search($closed, $availableSteps, true);
				unset($availableSteps[$key]);
			}
		}
		return $availableSteps;
	}
	
	protected function calcStepPrice($startPoint, $endPoint)
    {
        $startPointEdge = $startPoint;
		$endPointEdge = $endPoint;
        while($startPointEdge % $this->fieldSize !== 0) {
		    $startPointEdge++;
		}
		while($endPointEdge % $this->fieldSize !== 0) {
		    $endPointEdge++;
		}
		$verticalDiff = abs($startPointEdge - $endPointEdge) / $this->fieldSize;
		$horizontalDiff = abs(($startPointEdge - $startPoint) - ($endPointEdge - $endPoint));
		return ($verticalDiff + $horizontalDiff) * 10;
    }
	
	protected function findNearestEnemy(array $enemies)
	{
	    $enemiesPrices = [];
	    foreach($enemies as $enemy) {
		    $enemiesPrices[$this->calcStepPrice($this->position, $enemy->getPosition())] = $enemy;	
		}
		return $enemiesPrices[min(array_keys($enemiesPrices))];
    }
	
	protected function setPricesOfSteps(array $enemies, array $availableSteps)
	{
	    $pricesOfSteps = [];
	    $endingPosition = $this->findNearestEnemy($enemies)->getPosition();
		foreach($availableSteps as $step) {
		    $price = $this->calcStepPrice($step, $endingPosition);
			$pricesOfSteps[$step] = $price;
		}
		return $pricesOfSteps;
	}
}


class Mouse extends Animal
{
	private $isAlive = true;
	private $isProtected;
	
    private function findVisibleField($sideSize)
	{ 
	    $upBoundary = $this->position;
		$upCounter = 0;
		while($upBoundary > $this->fieldSize && $upCounter < ($sideSize - 1) / 2) {
		    $upBoundary -= $this->fieldSize;
			$upCounter++;
		}
		$leftEdge = $upBoundary;
		$counter = 0;
		while($leftEdge % $this->fieldSize !== 1 && $counter < ($sideSize - 1) / 2) {
		    $leftEdge--;
			$counter++;
		}
		$rightEdge = $upBoundary;
		$counter = 0;
		while($rightEdge % $this->fieldSize !== 0 && $counter < ($sideSize - 1) / 2) {
		    $rightEdge++;
			$counter++;
		}
		$downBoundary = $this->position;
		$downCounter = 0;
		while(($downBoundary + $this->fieldSize) < pow($this->fieldSize, 2) && 
		       $downCounter < ($sideSize - 1) / 2) {
		    $downBoundary += $this->fieldSize;
			$downCounter++;
		}
		$numRows = $downCounter + $upCounter;
		$visibleField = range($leftEdge, $rightEdge);
		for($i = 0; $i < count(range($leftEdge, $rightEdge)); $i++) {
		    $visibleField = array_merge($visibleField, range(($visibleField[$i] + $this->fieldSize) , 
			                         $visibleField[$i] + $this->fieldSize * $numRows,
									 $this->fieldSize));
		}
		return $visibleField;
	}
	
	private function checkProtection(array $sameSpecies) 
	{
	    $sameSpeciesPositions = [];
		foreach($sameSpecies as $same) {
		    $sameSpeciesPositions[] = $same->getPosition();
		}
	    $area = array_merge($this->findDiagonalSteps, $this->findOrthogonalSteps);
	    return (count(array_intersect($area, $sameSpeciesPositions)) >= 2) ? $this->isProtected = true 
	                                                                       : $this->isProtected = false;
	}
	
	public function isProtected()
	{
	    return $this->isProtected;
	}
	
	private function getDogsProtection(array $dogs)
	{
	    $visibleField = $this->findVisibleField(5);
	    $dogsPositions = [];
		foreach($dogs as $dog) {
		   	$dogsPositions[] = $dog->getPosition();
		}
	    if(array_intersect($visibleField, $dogsPositions)) {
	        return true;  	    
	    }
	    return false;
	}
	
	public function makeStep(array $enemies, array $neutrals, array $dogs)
	{
	    $availableSteps = $this->findOrthogonalSteps();
		$availableSteps = $this->excludeClosedPositions($neutrals, $availableSteps);
		$availableSteps[] = $this->position;	 
		$this->checkProtection($neutrals);
		$enemyPositions = [];
		foreach($enemies as $enemy) {
		    $enemyPositions[] = $enemy->getPosition();
		}
		$visibleEnemies = array_intersect($enemyPositions, $this->findVisibleField(9));
		if($this->getDogsProtection($dogs)) {
		    $pricesOfSteps = $this->setPricesOfSteps($dogs, $availableSteps);
			$this->position = array_search(min($pricesOfSteps), $pricesOfSteps, true);
		} else if($visibleEnemies) {
		    $pricesOfSteps = $this->setPricesOfSteps($enemies, $availableSteps);
			$this->position = array_search(max($pricesOfSteps), $pricesOfSteps, true);
		} else {
		    $this->position = array_rand(array_flip($availableSteps));
		}
	}
	
    public function setState($state) 
	{
	    $this->isAlive = $state;
	}
	
	public function getState()
	{
	    return $this->isAlive;
	}
}


class Cat extends Animal
{
    private $stepsToSleepCounter = 1;
	private $sleepy = false;
	
	public function isSleepy()
	{
	    return $this->sleepy;
	}
	
	public function makeStep(array $enemies, array $neutrals, array $dogs)
	{ 
	    if($this->isSleepy()) {
		    $this->sleepy = false;
		    $this->stepsToSleepCounter = 0;
		} else {
		    $availableSteps = array_merge($this->findOrthogonalSteps(), $this->findDiagonalSteps());
			$availableSteps = $this->excludeClosedPositions($neutrals, $availableSteps);
			$availableSteps[] = $this->position;	 
		    $pricesOfSteps = $this->setPricesOfSteps($enemies, $availableSteps);
		    $nearestEnemy = $this->findNearestEnemy($enemies);
			$this->position = array_search(min($pricesOfSteps), $pricesOfSteps, true);
			$this->stepsToSleepCounter++;
			$dogsAdjacentPositions = [];
			foreach($dogs as $dog) {
		    	$dogsAdjacentPositions = array_merge($dogsAdjacentPositions, $dog->getAdjacentPositions());
			}
	    	$dangerousPositions = array_intersect($dogsAdjacentPositions, $availableSteps);
			if($dangerousPositions) {
		    	foreach($dangerousPositions as $closed) {
			    	$key = array_search($closed, $availableSteps, true);
					unset($availableSteps[$key]);
				}
			}
            if($this->position === $nearestEnemy->getPosition()) {
				$nearestEnemy->setState(false);
				$this->sleepy = true;
				$this->stepsToSleepCounter = 0;
			} else if($this->stepsToSleepCounter === 8) {		
				$this->sleepy = true;
				$this->stepsToSleepCounter = 0;
			} else if($nearestEnemy->isProtected()) {
				$this->position = array_search(max($pricesOfSteps), $pricesOfSteps, true);
			}	
		}	
	}
}


class Dog extends Animal
{
    private function findAvailableSteps()
	{
	    $availableSteps = [];
	    if($this->position > $this->fieldSize * 2) {	
	        $availableSteps[] = $this->position - $this->fieldSize * 2;
		}
		if($this->position % $this->fieldSize !== 0 &&
		   ($this->position + 1) % $this->fieldSize !== 0) {
		    $availableSteps[] = $this->position + 2;
		}
		if(pow($this->fieldSize, 2) - $this->position >= $this->fieldSize * 2) {
		    $availableSteps[] = $this->position + $this->fieldSize * 2;
		}	
		if(($this->position - 1) % $this->fieldSize !== 0 &&
		   ($this->position - 2) % $this->fieldSize !== 0) {
		    $availableSteps[] = $this->position - 2;
		}
	    if($this->position > $this->fieldSize * 2 && 
		   $this->position % $this->fieldSize !== 0 &&
		   ($this->position + 1) % $this->fieldSize !== 0) {
           	$availableSteps[] = $this->position - $this->fieldSize * 2 + 2;
		}
		if($this->position > $this->fieldSize * 2 && 
		   ($this->position - 1) % $this->fieldSize !== 0 &&
		   ($this->position - 2) % $this->fieldSize !== 0) {	
		    $availableSteps[] = $this->position - $this->fieldSize * 2 - 2;
		}
		if(pow($this->fieldSize, 2) - $this->position >= $this->fieldSize * 2 && 
		   $this->position % $this->fieldSize !== 0 &&
		   ($this->position + 1) % $this->fieldSize !== 0) {
            $availableSteps[] = $this->position + $this->fieldSize * 2 + 2;
		}
		if(pow($this->fieldSize, 2) - $this->position >= $this->fieldSize * 2 && 
		   ($this->position - 1) % $this->fieldSize !== 0 &&
		   ($this->position - 2) % $this->fieldSize !== 0) {
            $availableSteps[] = $this->position + $this->fieldSize * 2 - 2;
		}
		return $availableSteps;
	}
	
	public function makeStep(array $cats, array $mouses, array $dogs)
	{
        $availableSteps = $this->findAvailableSteps();
	    $availableSteps = $this->excludeClosedPositions(array_merge($cats, $mouses, $dogs),
	                                                    $availableSteps);
        $availableSteps[] = $this->position;	                                                    
	    $this->position = array_rand(array_flip($availableSteps));
	}
	
	public function getAdjacentPositions()
	{
	    return array_merge($this->findOrthogonalSteps(), $this->findDiagonalSteps());
	}
}


class Game
{
    private $numMouses;
    private $numCats;
	private $numDogs;
    private $fieldSize;
    private $numSteps;
    private $animals = [];
    private $field;
	private $stepNumber = 1;
	
    public function __construct($numMouses, $numCats, $numDogs, $fieldSize, $numSteps)
    {
	    $this->numMouses = $numMouses;
		$this->numCats = $numCats;
		$this->numDogs = $numDogs;
		$this->fieldSize = $fieldSize;
		$this->numSteps = $numSteps;
		$this->field = new Field($fieldSize);
	}	
	
	private function createAnimals($limit, $animalType) 
	{
	    for($i = 0; $i < $limit; $i++) {
		    $this->animals[] = new $animalType($this->fieldSize);
		}	
    }
	
	private function getAnimals($animalType)
	{
	    $animals = [];
	    foreach($this->animals as $animal) {
		    if(get_class($animal) === $animalType) {
			    $animals[] = $animal;
			}
		}
		return $animals;
	}
	
	private function animalsMakeSteps($animalClass, array $enemies, array $neutrals, array $dogs)
	{
	    foreach($this->animals as $animal) {
		    if(get_class($animal) === $animalClass) {
			    $animal->makeStep($enemies, $neutrals, $dogs);
			}
		}
	}
	
	private function drawFieldAndAnimals()
	{
	    $this->field->drawFieldSchema();
		$this->field->drawAnimals();
	}
	
	private function removeDeadMouses()
	{
	    foreach($this->animals as $animal) {
		    if(get_class($animal) === "Mouse") {
			    if($animal->getState() === false) {
				    $key = array_search($animal, $this->animals, true);
					unset($this->animals[$key]);
					$this->field->removeAnimal($animal);
				}
			}
		}
	}
	
	private function setAnimalPositions()
	{
	    $unavailable = [];
	    foreach($this->animals as $animal) {
			do {
				$position = rand(1, pow($this->fieldSize, 2));
				$animal->setPosition($position);
			} while(in_array($position, $unavailable, true));
		    $unavailable[] = $animal->getPosition();
			$this->field->addAnimal($animal);
		}	
	}
	
	private function makeReport()
	{
	    $this->field->concatenateToShema("\tХод: " . $this->stepNumber, 1);
		$this->field->concatenateToShema("\tМышек: " . count($this->getAnimals("Mouse")), 2);
		$this->field->concatenateToShema("\tКошек: " . count($this->getAnimals("Cat")), 3);
		$this->field->concatenateToShema("\tСобак: " . count($this->getAnimals("Dog")), 4);
	}
	
	public function start()
	{
	    $this->createAnimals($this->numMouses, "Mouse");
	    $this->createAnimals($this->numCats, "Cat");
		$this->createAnimals($this->numDogs, "Dog");
		$this->setAnimalPositions();
		$this->drawFieldAndAnimals();
		$this->makeReport();
		echo $this->field;
		echo "\n";
		for($i = 1; $i < $this->numSteps; $i++) {
			$this->animalsMakeSteps("Mouse", $this->getAnimals("Cat"), 
			                                 $this->getAnimals("Mouse"), 
			                                 $this->getAnimals("Dog"));
			$this->animalsMakeSteps("Cat", $this->getAnimals("Mouse"), 
			                               $this->getAnimals("Cat"),
			                               $this->getAnimals("Dog"));
			$this->animalsMakeSteps("Dog", $this->getAnimals("Cat"), 
			                               $this->getAnimals("Mouse"), 
			                               $this->getAnimals("Dog"));
			$this->removeDeadMouses();
			$this->drawFieldAndAnimals();
			$this->stepNumber++;
			$this->makeReport();
			echo $this->field;
			echo "\n";
			if(count($this->getAnimals("Mouse")) === 0) {
			    break;
			}
		}	
	}
}


$game = new Game(4, 2, 1, 15, 25);
$game->start();