只有64分,1~6的测试点都过不了,全都超时,有没有神犇看看可不可以优化啊!
#include <iostream>
using namespace std;
bool floorState[205] = {0}; //记录楼层状态(这条有没有被搜索)
int floorStep[205] = {0};
int N, A, B;
int step = 0x7fffff;
void dfs(int now, int sum)
{
if (now == B)
{
step = min(step, sum);
}
//因为寻找的是最短路径
if (sum > step)
{
return;
}
floorState[now] = 1; //该层被搜索
if (now + floorStep[now] <= N && !floorState[now + floorStep[now]])
{
dfs(now + floorStep[now], sum + 1);
}
if (now - floorStep[now] > 0 && !floorState[now-floorStep[now]])
{
dfs(now - floorStep[now], sum + 1);
}
//实际上上面那两个已经把当前楼层的情况搜完了
//因此下面需要回溯到新的路径时,需要重置状态
floorState[now] = 0;
}
int main()
{
cin >> N >> A >> B;
for (int i = 1; i <= N; i++)
{
cin >> floorStep[i];
}
dfs(A, 0);
if (step != 0x7fffff)
{
cout << step;
}
else{
cout << -1;
}
return 0;
}
感谢神犇们!帮助答疑会关注