这个题目跟亚麻的新OA题有点像,不过评分是Hard。 我觉得这题非常经典可以仔细研究一下。
首先很明显求最短路线基本就是用BFS。然后neighbor如果是0就是不能走,如果是1或者heights就可以走。
有一个比较难的地方就是跟普通BFS不太一样,有一个走路的优先顺序。
比较Tricky的地方是,你下一个砍的tree必须是global 最小的next one。不是说你周围最小的。所以答案是先排序了一下下一个目标是多少。然后用BFS判断有没有办法从当前地方过去。只要一个地方去不到就return -1.
经过好几道题的BFS,发现所有BFS类code完全一样,可以用模板!
这题最经典的就是变化起点的方法, start[0] = tree[0]; start[1] = tree[1]. 简直不能再厉害