Resolution Exo 7 - Jeu de la vie - PHP - Meilleurdevdefrance 2015

gistfile1.php

<?php

/*******
 * Read input from STDIN
 * Use echo or print to output your result, use the PHP_EOL constant at the end of each result line.
 * Use:
 *      local_echo( $variable ); 
 * to display simple variables in a dedicated area.
 * 
 * Use:
 *      local_print_r( $array ); 
 * to display arrays in a dedicated area.
 * ***/
 
$input = array();
while( $f = stream_get_line(STDIN, 10000, PHP_EOL) ) {
    $input[] = $f;
    /* Lisez les données et effectuez votre traitement */
}

/* Vous pouvez aussi effectuer votre traitement ici après avoir lu toutes les données */

set_time_limit(120);

$nb = array_shift($input);

// traitement de l'input
$sortInput = [];

while($line = array_shift($input)) {
    list($x1,$y1, $x2, $y2) = explode(' ', $line);

    $index = $x1 + $y1;
    if (empty($sortInput[$index])) {
        $sortInput[$index] = [];
    }
    $sortInput[$index][] = $line;
}
unset($input);
ksort($sortInput);


function find($start, array $already, $x1, $y1, $x2, $y2) {
    global $sortInput;
    foreach($sortInput as $k => &$line) {
        if ($k < $start) {continue;}

        foreach($line as $k2 => &$row) {
            if (array_search($row, $already) !== false) {continue;}
            list($a1, $b1, $a2, $b2) = explode(' ', $row);
             if ((($x1 + 1) <= $a1 && $x2 + 1 >= $a1
                    && ($y1 - 1) <= $b2 && ($y1-1) >= $b1)
                || ($a1<=$x2 && $a2 >= $x1 && $b1<=$y2 && $b2 >= $y1)
                || ($a1 <= ($x1) && $a2 >= ($x1)
                    && ($y1 + 1) <= $b1 && ($y2 + 1) >= $b1)
            ){
                $already[] = $row;
                $already = find($start, $already, $a1, $b1, $a2, $b2);
                unset($line[$k2]);
            }
        }
    }

    return $already;
}

$result  = 0;
foreach($sortInput as $start => &$row) {

    foreach($row as &$line) {
        list($x1, $y1, $x2, $y2) = explode(' ', $line);

        $found = find($start, [$line], $x1, $y1, $x2, $y2);

        $x = 0;
        $y = 0;

        foreach ($found as $keep) {
            list($a1, $b1, $a2, $b2) = explode(' ', $keep);
            $x = max($x, $a2);
            $y = max($y, $b2);
        }

        $result = max(($x - $x1) + ($y - $y1) + 1, $result);
    }
}
echo $result;


?>