64分求助!悬赏关注!
查看原帖
64分求助!悬赏关注!
1108111
XYY62012楼主2024/3/17 16:10

大佬帮个忙啊!

只有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;
}

感谢神犇们!帮助答疑会关注

2024/3/17 16:10
加载中...