题目
牛牛来到训练场里闯关,他的宝剑的耐久度降到了 2,这意味着牛牛最多只能打倒 2 只怪兽,否则将会被淘汰。
训练场的地图可以看作一棵以 1 为根节点的树,训练场的终点为这棵树的叶子结点,树上的每个结点最多有一只怪兽,结点与结点间的边上没有怪兽。
每一个有怪兽的结点上牛牛都需要打倒怪兽才算安全,并且牛牛一旦选定好打怪路线之后便不能走回头路。
请问牛牛有多少种到达终点且不被淘汰的路径。
解题思路
使用 DFS 算法。
到达某个点时,判断此时的宝剑耐久度是否大于等于 0 且是否是叶子节点,若是,则累加计入 。
C++代码
/** * struct Point { * int x; * int y; * }; */ class Solution { int ans = 0; vector<vector<int>> edges; vector<int> vis; void dfs(int a, int cnt, vector<int>& f){ cnt -= f[a-1]; if(cnt < 0) return; bool isLeaf = true; for(auto b : edges[a]){ if(!vis[b]){ isLeaf = false; vis[b] = true; dfs(b, cnt, f); } } if(isLeaf) ++ans; } public: /** * 返回牛牛能到达终点且不被淘汰的路径数 * @param n int整型 * @param Edge Point类vector * @param f int整型vector * @return int整型 */ int solve(int n, vector<Point>& Edge, vector<int>& f) { // write code here edges.resize(n+1); for(int i=0; i<Edge.size(); ++i){ int u = Edge[i].x; int v = Edge[i].y; edges[u].push_back(v); edges[v].push_back(u); } ans = 0; vis.resize(n+1, false); vis[1] = true; dfs(1, 2, f); return ans; } };