Last active
March 26, 2019 22:11
-
-
Save dib258/a83925ab42daeb83637984a3433667cf to your computer and use it in GitHub Desktop.
Boss Video Game Richest
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?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 */ | |
?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment