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

叁歲伎倆 2022-04-03 16:42 180阅读 0赞

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

题目是这样的:

王者农药新模式一“智慧王者”， 提供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"  
    \]

\---------------------   
原文：https://blog.csdn.net/qq\_39307131/article/details/82151935