Boss Video Game Richest

exo3.php

<?php
ini_set('memory_limit', '8192M');
/*******
 * Read input from STDIN
 * Use echo or print to output your result to STDOUT, use the PHP_EOL constant at the end of each result line.
 * Use:
 *     fwrite(STDERR, "hello, world!" . PHP_EOL);
 * or
 *		error_log("hello, world!" . PHP_EOL);
 * to output debugging information to STDERR
 * ***/

do{
    $f = stream_get_line(STDIN, 10000, PHP_EOL);
    if($f!==false){
        $input[] = $f;
    }
}while($f!==false);

function createMatrix($n, $input) {
    $matrix = [];
    $empty = [];
    $itemToTake = 0;

    for ($i = 0; $i < $n; $i++) {
        $matrix[$i] = [];
        $empty[$i] = [];
        $line = str_split($input[$i+1]);
        for ($j = 0; $j < count($line); $j++) {
            if ($line[$j] != '.') {
                $itemToTake++;
            }
            $matrix[$i][$j] = $line[$j];
            $empty[$i][$j] = 0;
        }
    }

    return [$matrix, $empty, $itemToTake];
}

function isSafe($x, $y, $n, $guard) {
    if (
        $x >= 0 &&
        $y >= 0 &&
        $x < $n &&
        $y < $n
    ) {
        if (!$guard[$x][$y]) {
            return true;
        }
    }
    return false;
}

function backTrack(array $matrix, $n, $x, $y, $path, $totalMoney, $totalItem, array $guard, array &$empty) {
    var_dump($path);
    // nothing more to take
    if (!$totalItem) {
        return [$totalMoney, $path];
    } else {
        $returnValue = [];
        $guard[$x][$y] = 1;

        // var_dump('Case type : '.$matrix[$x][$y]);
        //is there something on the ground
        if ($matrix[$x][$y] != '.') {
            var_dump('taken');
            if ($matrix[$x][$y] == 'o') {
                $totalMoney++;
            } else if ($matrix[$x][$y] == '*') {
                $totalMoney *= 2;
            }

            $matrix[$x][$y] = '.';
            $totalItem--;

            $path .= 'x';

            // $returnValue['valueTake'] = backTrack($matrix, $n, $x, $y, $path.'x', $totalMoney, $totalItem, $empty, $empty);
            // if (!is_array($returnValue['valueTake'])) {
            //     return false;
            // }
        } else {
            // var_dump('taking not possible');
        }

        // test if possible to move up
        if (isSafe($x, $y-1, $n, $guard)) {
            // var_dump('move up');
            // try to move up
            $returnValue['valueUp'] = backTrack($matrix, $n, $x, $y-1, $path.'^', $totalMoney, $totalItem, $guard, $empty);
            // if (!is_array($returnValue['valueUp'])) {
            //     return false;
            // }
        } else {
            // var_dump('moving up not possible');
        }
        
        // test if possible to move down
        if (isSafe($x, $y+1, $n, $guard)) {
            // try to move down
            // var_dump('move down');
            
            $returnValue['valueDown'] = backTrack($matrix, $n, $x, $y+1, $path.'v', $totalMoney, $totalItem, $guard, $empty);
            // if (!is_array($returnValue['valueDown'])) {
            //     return false;
            // }
        } else {
            // var_dump('moving down not possible');
        }

        // test if possible to move left
        if (isSafe($x-1, $y, $n, $guard)) {
            // var_dump('move left');
            // try to move left
            $returnValue['valueLeft'] = backTrack($matrix, $n, $x-1, $y, $path.'<', $totalMoney, $totalItem, $guard, $empty);
            // if (!is_array($returnValue['valueLeft'])) {
            //     return false;
            // }
        } else {
            // var_dump('moving left not possible');
        }
        
        // test if possible to move right
        if (isSafe($x+1, $y, $n, $guard)) {
            // try to move right
            // var_dump('move right');
            
            $returnValue['valueRight'] = backTrack($matrix, $n, $x+1, $y, $path.'>', $totalMoney, $totalItem, $guard, $empty);
            // if (!is_array($returnValue['valueRight'])) {
            //     return false;
            // }
        } else {
            // var_dump('moving right not possible');
        }

        $max = 0;
        $nameToReturn = '';

        var_dump($returnValue);

        foreach($returnValue as $name => $value) {
            if ($value[0] > $max) {
                $max = $value[0];
                $nameToReturn = $name;
            }
        }
        if ($nameToReturn == '') {
            return false;
        } else {
            return $returnValue[$nameToReturn];
        }
    }
}

function findPathToGetRich($input) {
    $n = $input[0];
    $alreadySearchedPath = [];
    $totalMoney = 0;
    $currentElementTaken = 0;
    list($matrix, $empty, $totalItemToTake) = createMatrix($n, $input);

    $solution = backTrack($matrix, $n, 0, 0, '', 0, $totalItemToTake, $empty, $empty);
    if (!is_array($solution)) {
        return 'no solution';
    }

    return $solution[1];
}

echo findPathToGetRich($input);


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