给你一个非负整数数组，里面的值表示当前位置能够跳的最远距离，现在每次都从参数0开始跳，请问能跳到终点吗？
样例：
输入：[2,3,1,1,4]
输出：true
输入：[3,2,1,0,4]
输出：false
参考代码：dfs直接解
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<int> nums;
bool sign = false;
void trans(string &str) {
int n = str.size() - 1;
int i = 1;
while (i < n) {
int loc = i;
while (i < n&&str[i] != ',')
++i;
string s = str.substr(loc, i - loc);
nums.push_back(stoi(s));
++i;
}
}
void isReach(int i) {
if (i == nums.size() - 1) {
sign = true;
return;
}
int n = nums[i];
for (int k = 1; k <= n; ++k) {
i += k;
isReach(i);
i -= k;
}
}
int main() {
string str;
getline(cin, str);
trans(str);
isReach(0);
if (sign)
cout << "true" << endl;
else
cout << "false" << endl;
} 
全部评论
(0) 回帖