王者农药新模式——智慧王者 树形递归

 今天做了道题,感觉是挺经典的递归，所以就记录了下来。没有做优化！！！

题目是这样的:

      王者农药新模式一“智慧王者”， 提供5个英雄，假设各自血量和攻击力如下:

梦琪:  10000血，  100攻程咬金:  5000血，200攻亚瑟: 2000血，  500攻铠: 1000血，1000攻狄仁杰:  100血，2000攻

      地图被画成一张MxN的棋盘，左上角为英雄的出生地，右下角则为敌方基地。所有的格子中，要么是“敌方水晶塔”，要么是“回血包”。其中，敌方水晶塔会对英雄造成X点伤害，  每个水晶塔有自己独立的伤害值，而加血卷轴可以恢复英雄的血量。当英雄的血量小于等于0时，  英雄死亡，游戏结束。英雄每次只能向下或向右移动一个格子，直到达到敌方基地的格子，摧毁基地取得胜利。

      如果给定一张随机生成的地图如下，其中，负数代表敌方水晶塔的伤害值，正数代表恢复血量值: 

 

问：

1、选择哪个英雄，既可以保证胜利，又能提供最大攻击力?请给出算法，在任意随机地图下都有效。亦即，地图随机生成，针对每一种随机地图，算法都可以给出英雄选择。

2、如上图给定的地图，  应该选择哪一个英雄?

3、请给出以，上算法所计算的最优路线。

解题思路:

这道题很明显是考察二叉树的，解题方向是树形递归。

下面直接看代码：

<?php echo "<pre>"; // 地图 $letters = [ [133, -523, -558, 846, -907, -1224, -1346, 787, -411, -1826], [-1478, -853, -1401, 341, -26, 759, -444, 174, -1594, -2000], [861, -584, 670, 696, 676, -1674, -1737, -1407, -484, 246], [133, -1669, -419, -382, -895, 732, -1278, -1802, -527, 862], [133, 544, -1943, 563, -380, -1268, 266, -1309, -1946, 85], [133, -1631, -168, 741, -211, -1070, -1873, -554, 243, -901], [133, 971, -21, -1111, 463, 944, -127, -1414, -1463, -1287], [133, -1886, -1159, -73, 555, -426, -190, -1750, -1028, -188], [133, -1654, -931, -1100, -433, -1643, -1281, -455, 904, -126], [-1494, -632, 243, 90, 993, 322, 32, -388, -225, 952], ]; // 英雄 $people = [ 'mq' => [10000,100], 'cyj' => [5000,200], 'ys' => [2000,500], 'k' => [1000,1000], 'drj' => [100,2000], ]; $arr = targets($people, $letters); //var_dump($arr); good($arr); //寻找路线的方法 function targets($people, &$letters, $arr = []) { if(empty($arr)){ $arr['people'] = $people; // 记录英雄血量值,攻击值 $arr['x'] = 0; // 横向坐标 $arr['y'] = 0; // 纵向坐标 $arr['xy'] = []; // 走过的坐标路线 } //英雄伤害计算 $people = []; foreach ($arr['people'] as $key => $value){ //计算英雄血量 $value[0] += $letters[$arr['y']][$arr['x']]; if($value[0] > 0) $people[$key] = $value; } $arr['xy'][] = (string)$arr['x'] .','. (string)$arr['y']; $arr['people'] = $people; //中途 英雄全部死亡 if(empty($people)) return []; $xLen = count($letters[0]); //横向深度 $yLen = count($letters); //纵向深度 //到达终点 返回路线 英雄血量 if($arr['x']+1 >= $xLen && $arr['y']+1 >= $yLen){ return [$arr]; } $xArr = $yArr = $arr; $end1 = $end2 = []; //向右 if($xArr['x']+1 < $xLen){ $xArr['x']++; // 横向坐标 $end1 = targets($people, $letters, $xArr); } //向下 if($yArr['y']+1 < $yLen){ $yArr['y']++; // 纵向坐标 $end2 = targets($people, $letters, $yArr); } $end = array_merge($end1, $end2); //返回所有能通过的路线 return $end; } // 筛选出最佳路线 function good($arr) { $max = 0; $route = []; foreach ($arr as $value){ if($value['people']['mq'][0] > $max){ $max = $value['people']['mq'][0]; $route = $value; } } echo json_encode($route); }

 下面是输出结果

{ "people":{ "mq":[ 13917, 100 ], "cyj":[ 8917, 200 ], "ys":[ 5917, 500 ], "k":[ 4917, 1000 ] }, "x":9, "y":9, "xy":[ "0,0", "1,0", "2,0", "3,0", "3,1", "3,2", "3,3", "3,4", "3,5", "4,5", "4,6", "4,7", "4,8", "4,9", "5,9", "6,9", "7,9", "8,9", "9,9" ] }