<?php
/*
* Комната 0 введена для унификации алгоритма.
* Из неё можно попаст в любой выход, в неё попасть из других комнат нельзя.
*/
const NODES = [
0 => ['battleTime' => 0, 'loot' => 0],
1 => ['battleTime' => 5, 'loot' => 15],
2 => ['battleTime' => 2, 'loot' => 1],
3 => ['battleTime' => 3, 'loot' => 5],
4 => ['battleTime' => 3, 'loot' => 6],
5 => ['battleTime' => 4, 'loot' => 7],
6 => ['battleTime' => 5, 'loot' => 9],
7 => ['battleTime' => 7, 'loot' => 16],
8 => ['battleTime' => 2, 'loot' => 3],
9 => ['battleTime' => 0, 'loot' => 0],
10 => ['battleTime' => 0, 'loot' => 0],
];
const ROUTE_TIMES = [
0 => [9 => 0, 10 => 0],
1 => [2 => 1],
2 => [1 => 1, 8 => 2, 9 => 3, 4 => 1],
3 => [9 => 2, 4 => 4],
4 => [3 => 4, 2 => 1, 5 => 3],
5 => [4 => 3, 10 => 1],
6 => [10 => 4, 7 => 4],
7 => [8 => 4, 6 => 4],
8 => [2 => 2, 7 => 4, 10 => 6],
9 => [3 => 2, 2 => 3],
10 => [5 => 1, 8 => 6, 6 => 4],
];
const MAX_LIFETIME = 25;
function findRoute(array $state): array
{
$bestState = $state;
foreach (ROUTE_TIMES[$state['currentNode']] as $nextNode => $travelTime) {
$nodeTime = $state['lifetime'] + $travelTime +
(in_array($nextNode, $state['route']) ? 0 : NODES[$nextNode]['battleTime']);
if ($nodeTime > MAX_LIFETIME) {
continue;
}
$nodeState = findRoute([
'lifetime' => $nodeTime,
'currentNode' => $nextNode,
'wealth' => $state['wealth'] + (in_array($nextNode, $state['route']) ? 0 : NODES[$nextNode]['loot']),
'route' => [...$state['route'], $nextNode],
]);
if ($nodeState['wealth'] > $bestState['wealth']) {
$bestState = $nodeState;
}
}
return $bestState;
}
$state = findRoute([
'lifetime' => 0,
'currentNode' => 0,
'wealth' => 0,
'route' => [],
]);
echo "Route: ", implode(' => ', array_reverse($state['route'])), "\n";
echo "Wealth: ", $state['wealth'], "\n";
echo "Time: ", $state['lifetime'], "\n";
Route: 8 => 2 => 1 => 2 => 4 => 5 => 10
Wealth: 32
Time: 25
