<?php


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


abstract class Animal
{
    protected $xPoint;
	protected $yPoint;
	protected $field;
	
	public function __construct(Field $field)
	{
	    $this->field = $field;
	}
	
	public function getPosition()
	{
	    return [$this->xPoint, $this->yPoint];
	}
	
	public function setPosition($x, $y)
	{
	    $this->xPoint = $x;
		$this->yPoint = $y;
	}
	
	public function getLabel()
	{
	    return $this->label;
	}
	
	protected function findOrthogonalSteps()
	{
	    $orthogonalSteps = [];
	    if($this->xPoint !== 0) {
		    $orthogonalSteps[] = [$this->xPoint - 1, $this->yPoint];
		}
		if($this->yPoint !== 0) {
		    $orthogonalSteps[] = [$this->xPoint, $this->yPoint - 1];
		}
		if($this->xPoint !== $this->field->getSize()) {
		    $orthogonalSteps[] = [$this->xPoint + 1, $this->yPoint];
		}
		if($this->yPoint !== $this->field->getSize()) {
		    $orthogonalSteps[] = [$this->xPoint, $this->yPoint + 1];
		}
		return $orthogonalSteps;
	}
	
	protected function findDiagonalSteps()
	{
	    $diagonalSteps = [];
	    if($this->xPoint !== 0 && $this->yPoint !== 0) {
		    $diagonalSteps[] = [$this->xPoint - 1, $this->yPoint - 1];
		}
		if($this->yPoint !== 0 && $this->xPoint !== $this->field->getSize()) {
		    $diagonalSteps[] = [$this->xPoint + 1, $this->yPoint - 1];
		}
		if($this->yPoint !== $this->field->getSize() && 
		   $this->xPoint !== $this->field->getSize()) {
		    $diagonalSteps[] = [$this->xPoint + 1, $this->yPoint + 1];
		}
		if($this->xPoint !== 0 && $this->yPoint !== $this->field->getSize()) {
		    $diagonalSteps[] = [$this->xPoint - 1, $this->yPoint + 1];
		}
		return $diagonalSteps;
	}
	
	protected function calcStepPrice(array $startPoint, array $endPoint)
    {
	    $horizontalDiff = abs($startPoint[0] - $endPoint[0]);
        $verticalDiff = abs($startPoint[1] - $endPoint[1]);
		return ($verticalDiff + $horizontalDiff) * 10;
    }
	
	protected function findNearestEnemy(array $enemies)
	{
	    $enemiesPrices = [];
	    foreach($enemies as $enemy) {
		    $enemiesPrices[$this->calcStepPrice($this->getPosition(), $enemy->getPosition())] = $enemy;	
		}
		return $enemiesPrices[min(array_keys($enemiesPrices))];
    }
		
	protected function excludeClosedPositions(array $animals, array $availableSteps)
	{
	    foreach($animals as $animal) {
		    if(in_array($animal->getPosition(), $availableSteps)) {
              	$key = array_search($animal->getPosition(), $availableSteps, true);
				unset($availableSteps[$key]);
			}	
		}
	    return $availableSteps;
	}
	
	protected function setPricesOfSteps(Animal $nearestEnemy, array $allys, array $dogs)
	{
	    $pricesOfSteps = [];
	    $endingPosition = $nearestEnemy->getPosition();
		$availableSteps = $this->findAvailableSteps($allys, $dogs);
		foreach($availableSteps as $step) {
		    $price = $this->calcStepPrice($step, $endingPosition);
			$pricesOfSteps[$price] = $step;
		}
		return $pricesOfSteps;
	}
}


class Mouse extends Animal
{
    protected $label = "M";
	private $visibleFieldRadius = 9;
	private $isProtected;
	private $isAlive = true;

	public function getState()
	{
	    return $this->isAlive;
	}
	
	public function setState($state)
	{
	    $this->isAlive = $state;
	}
	
    protected function findAvailableSteps($mouses, $dogs) 
	{
	    $availableSteps =  $this->findOrthogonalSteps();
		$availableSteps = $this->excludeClosedPositions(array_merge($mouses, $dogs), $availableSteps);
		$availableSteps[] = $this->getPosition();
	    return $availableSteps;
	} 
	
	private function findVisibleField($size)
	{
	    $radius = floor($size / 2);
	    $visibleField = [];
	    $leftBound = max(0, $this->xPoint - $radius); 
		$rightBound = min($this->xPoint + $radius, $this->field->getSize());
		$upBound = max(0, $this->yPoint - $radius);
		$downBound = min($this->yPoint + $radius, $this->field->getSize());
		$visibleField = [];
		for($i = $leftBound; $i <= $rightBound; $i++) {
		    for($j = $upBound; $j <= $downBound; $j++) {
			    $visibleField[] = [$i, $j]; 
			}
		}
		return $visibleField;
	}
	
	private function checkVisibleAnimals(array $animals, $radius) 
	{
	    $visibleAnimals = [];
		$visibleField = $this->findVisibleField($radius);
	    foreach($animals as $animal) {
		    if(in_array($animal->getPosition(), $visibleField)) {
			    $visibleAnimals[] = $animal;
			}	
		}
		return $visibleAnimals;
	}
	
	private function checkProtection(array $mouses) 
	{
	    $this->isProtected = false;
	    $mousesPos = [];
		foreach($mouses as $mouse) {
		    $mousesPos[] = $mouse->getPosition();
		}
	    $area = array_merge($this->findDiagonalSteps(), $this->findOrthogonalSteps());
		$counter = 0;
	    foreach($mousesPos as $position) {
		    if(in_array($position, $area)) {
			    $counter++;
			}
		}
		if($counter >= 2) {
		    $this->isProtected = true;
		}
	}
	
	public function isProtected()
	{
	    return $this->isProtected;
	}
		
	public function makeStep() 
	{
	    $cats = $this->field->getAnimalsByType("Cat");
		$mouses = $this->field->getAnimalsByType("Mouse");
		$dogs = $this->field->getAnimalsByType("Dog");
		$this->checkProtection($mouses);
        $visibleCats = $this->checkVisibleAnimals($cats, 9);
		if($visibleCats) {
		    $nearestEnemy = $this->findNearestEnemy($visibleCats);
			$pricesOfSteps = $this->setPricesOfSteps($nearestEnemy, $mouses, $dogs);
			$position = $pricesOfSteps[max(array_keys($pricesOfSteps))];
			$this->xPoint = $position[0];
			$this->yPoint = $position[1];
		} else {
		    $availableSteps = $this->findAvailableSteps($mouses, $dogs);
		    $positionIndex = array_rand($availableSteps);
			$position = $availableSteps[$positionIndex];
			$this->xPoint = $position[0];
			$this->yPoint = $position[1];
		}
	}
}


class Cat extends Animal
{
    protected $label = "K";
    private $stepsToSleepCounter = 1;
	private $sleepy = false;
	
	protected function findAvailableSteps($cats, $dogs) 
	{
	    $availableSteps = array_merge($this->findOrthogonalSteps(), $this->findDiagonalSteps());
        $availableSteps = $this->excludeClosedPositions($cats, $availableSteps);
		$availableSteps[] = $this->getPosition();
		$availableSteps = $this->checkDogs($dogs, $availableSteps); 		
		$availableSteps[] = $this->getPosition();
	    return $availableSteps;
	}
	
	private function checkDogs(array $dogs, array $availableSteps)
	{
	    $dogsAdjacentPos = [];
	    foreach($dogs as $dog) {
		    $dogsAdjacentPos = array_merge($dogsAdjacentPos, $dog->getAdjacentPositions());
		}
		foreach($availableSteps as $step) {
		    if(in_array($step, $dogsAdjacentPos)) {
			    $key = array_search($step, $availableSteps, true); 
				unset($availableSteps[$key]);
			}
		}
		return $availableSteps;
 	}
	
	public function makeStep()
	{
	    if($this->label === "@") {
		    $this->label = "K";
			$this->stepsToSleepCounter = 0;
		} else {
			$cats = $this->field->getAnimalsByType("Cat");
			$mouses = $this->field->getAnimalsByType("Mouse");
			$dogs = $this->field->getAnimalsByType("Dog");
			$nearestEnemy = $this->findNearestEnemy($mouses);
			$pricesOfSteps = $this->setPricesOfSteps($nearestEnemy, $cats, $dogs);
      	    $position = $pricesOfSteps[min(array_keys($pricesOfSteps))];
			$this->xPoint = $position[0];
			$this->yPoint = $position[1];
			$this->stepsToSleepCounter++;
            if($position === $nearestEnemy->getPosition()) {
				$nearestEnemy->setState(false);
				$this->label = "@";
				$this->stepsToSleepCounter = 0;
			} else if($this->stepsToSleepCounter === 8) {		
				$this->label = "@";
				$this->stepsToSleepCounter = 0;
			} else if($nearestEnemy->isProtected()) {
				$position = $pricesOfSteps[max(array_keys($pricesOfSteps))];
			} 				
		} 
	}
}


class Dog extends Animal
{
    protected $label = "C";
	
    private function findAvailableSteps()
	{
	    $availableSteps = [];
	    if($this->xPoint > 1) {
		    $availableSteps[] = [$this->xPoint - 2, $this->yPoint];
		}
		if($this->yPoint > 1) {
		    $availableSteps[] = [$this->xPoint, $this->yPoint - 2];
		}
		if($this->xPoint + 1 < $this->field->getSize())  {
		    $availableSteps[] = [$this->xPoint + 2, $this->yPoint];
		}
		if($this->yPoint + 1 < $this->field->getSize())  {
		    $availableSteps[] = [$this->xPoint, $this->yPoint + 2];
		}
		if($this->xPoint > 1 && $this->yPoint > 1) {
		    $availableSteps[] = [$this->xPoint - 2, $this->yPoint - 2];
		}
		if($this->yPoint > 1 && $this->xPoint + 1 < $this->field->getSize()) {
		    $availableSteps[] = [$this->xPoint + 2, $this->yPoint - 2];
		}
		if($this->yPoint + 1 < $this->field->getSize() && 
		   $this->xPoint + 1 < $this->field->getSize()) {
		    $availableSteps[] = [$this->xPoint + 2, $this->yPoint + 2];
		}
		if($this->xPoint > 1 && $this->yPoint + 1 < $this->field->getSize()) {
		    $availableSteps[] = [$this->xPoint - 2, $this->yPoint + 2];
		}
		return $availableSteps;
	}
	
	public function makeStep()
	{
	    $allAnimals = $this->field->getAnimals();
		$availableSteps = $this->findAvailableSteps();
		$availableSteps = $this->excludeClosedPositions($allAnimals, $availableSteps);
		$availableSteps[] = $this->getPosition();
		$positionIndex = array_rand($availableSteps);
		$position = $availableSteps[$positionIndex];
		$this->xPoint = $position[0];
		$this->yPoint = $position[1];
	}
	
	public function getAdjacentPositions()
	{
	    return array_merge($this->findDiagonalSteps(), $this->findOrthogonalSteps());
	}
}


class Field
{
    private $size;
	private $animals;
	
	public function __construct($size)
	{
	    $this->size = $size;
	}
	
	public function getAnimals()
	{
	    return $this->animals;
	}
	
	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 getSize()
	{
	    return $this->size;
	}
	
	private function drawSchema()
	{
	    $schema = [];
	    for($i = $this->size; $i >= 0; $i--) {
		    for($j = 0; $j <= $this->size; $j++) {
			    $schema[] = [$j, $i];
			}
		}
        foreach($this->animals as $animal) {
		    $key = array_search($animal->getPosition(), $schema, true);
			$schema[$key] = $animal->getLabel() . " ";
		}
		return $schema;
	}
	
	public function getAnimalsByType($animalType)
	{
	    $animals = [];
	    foreach($this->animals as $animal) {
		    if(get_class($animal) === $animalType) {
			    $animals[] = $animal;
			}
		}
		return $animals;
	}
	
	public function __toString()
	{
	    $schema = $this->drawSchema();
		foreach($schema as $elem) {
		    if(is_array($elem)) {
			    $key = array_search($elem, $schema, true);
                $schema[$key] = ". ";				
			}
		}
		$schema = implode("", $schema);
		$result = chunk_split($schema, ($this->size + 1) * 2, "\n");
	    return $result;
	}
}


class Game
{
    private $numMouses;
    private $numCats;
	private $numDogs;
    private $numSteps;
    private $field;
	private $stepNumber = 0;
	
    public function __construct($numMouses, $numCats, $numDogs, $fieldSize, $numSteps)
    {
	    $this->numMouses = $numMouses;
		$this->numCats = $numCats;
		$this->numDogs = $numDogs;
		$this->numSteps = $numSteps;
		$this->field = new Field($fieldSize);
	}	
	
	private function createAnimals($limit, $animalType) 
	{
	    for($i = 0; $i < $limit; $i++) {
		    $animal = new $animalType($this->field);
			$this->field->addAnimal($animal);
		}	
    }
	
	private function animalsMakeSteps($animalClass)
	{
	    foreach($this->field->getAnimals() as $animal) {
		    if(get_class($animal) === $animalClass) {
			    $animal->makeStep();
			}
		}
	}
	
	private function removeDeadMouses()
	{
	    foreach($this->field->getAnimals() as $animal) {
		    if(get_class($animal) === "Mouse") {
			    if($animal->getState() === false) {
					$this->field->removeAnimal($animal);
				}
			}
		}
	}
	
	private function setAnimalPositions()
	{
	    $unavailable = [];
	    foreach($this->field->getAnimals() as $animal) {
			do {
				$xPoint = rand(1, $this->field->getSize());
				$yPoint = rand(1, $this->field->getSize());
				$animal->setPosition($xPoint, $yPoint);
			} while(in_array([$xPoint, $yPoint], $unavailable, true));
		    $unavailable[] = $animal->getPosition();
		}
    }
	
	private function makeReport()
	{
	    $info = "Ход: " . $this->stepNumber . 
		        "\tМышек: " . count($this->field->getAnimalsByType("Mouse")) .
		        "\tКошек: " . count($this->field->getAnimalsByType("Cat")) . 
		        "\tСобак: " . count($this->field->getAnimalsByType("Dog"));
		return $info;		
	}
	
	public function start()
	{
	    $this->createAnimals($this->numMouses, "Mouse");
	    $this->createAnimals($this->numCats, "Cat");
		$this->createAnimals($this->numDogs, "Dog");
		$this->setAnimalPositions();
		$this->stepNumber++;
        echo $this->makeReport() . "\n" . $this->field . "\n";
		for($i = 1; $i < $this->numSteps; $i++) {
			$this->animalsMakeSteps("Mouse");
			$this->animalsMakeSteps("Cat");
			$this->animalsMakeSteps("Dog");
			$this->removeDeadMouses();
			$this->stepNumber++;
			echo $this->makeReport() . "\n" . $this->field . "\n";
			if(count($this->field->getAnimalsByType("Mouse")) === 0) {
			    break;
			}
		}	
	}    
}


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