HDU 1548的问题：A Strange Lift

Question

HDU 1548“A Strange Lift”（电梯问题）。本人刚学bfs和dfs还不会用STL库，就自己写了一个队列。自己测试了很多组数据觉得没有错误，但是提交上去就是Wrong Answer，检查了好多遍也检查不出问题。各位大神帮忙看一下我的代码哪里有错误或者漏洞，谢谢！

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int N,A,B,i;
int que[10010];
int vis[10010];
int step[10010];
int K[10010];

int main()
{
    while(scanf("%d",&N)!=EOF&&N!=0)
    {
        int first=0,stop=0;
        scanf("%d %d",&A,&B);
        for(i=1; i<N+1; i++)
            scanf("%d",&K[i]);
        memset(vis,0,sizeof(vis));
        memset(step,0,sizeof(step));
        que[stop++]=A;
        while(first<stop)
        {
            int temp=que[first++];
            if(temp==B)
                 break;
            if(temp+K[temp]<=N&&temp+K[temp]>0&&vis[temp+K[temp]]==0)
            {
                vis[temp+K[temp]]=1;
                que[stop++]=temp+K[temp];
                step[temp+K[temp]]=step[temp]+1;
            }
            if(temp-K[temp]>0&&temp-K[temp]<=N&&vis[temp-K[temp]]==0)
            {
                vis[temp-K[temp]]=1;
                que[stop++]=temp-K[temp];
                step[temp-K[temp]]=step[temp]+1;
            }
        }
        if(step[B]==0)
            if(A!=B)
            cout<<"-1"<<endl;
        else
            cout<<step[B]<<endl;
    }
    return 0;
}

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

你的代码有一些小问题：

1. que 是一个动态数组，你使用了它来存储待访问的节点。但是，当你尝试访问已经访问过的节点时，你需要先移除它。
2. 在循环中，你需要更新 que 和 vis 数组以避免重复访问。
3. step 数组用来记录每个节点的前驱节点数。你应该在循环结束后将其初始化为0。

下面是修复这些问题后的代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    int val;
    vector<int> pre;
};

Node create_node(int val) {
    Node node = {val, vector<int>()};
    return node;
}

void push(vector<Node>& nodes, int val) {
    auto it = upper_bound(nodes.begin(), nodes.end(), make_pair(val, -1));
    if (it == nodes.end()) {
        nodes.push_back(create_node(val));
    } else {
        (*it).pre.push_back(val);
    }
}

int dfs(Node& root, int val) {
    if (!root.val) {
        return 0;
    }

    int prev_val = root.pre.back();
    if (prev_val != -1 && prev_val == val) {
        return 0;
    }

    int result = 1 + dfs(root.pre.back(), val);

    if (result > 1) {
        root.pre.pop_back();
    }

    return result;
}

int main() {
    int n;
    cin >> n;
    vector<Node> nodes(n + 1);

    for (int i = 1; i <= n; ++i) {
        int a, b;
        cin >> a >> b;
        push(nodes, a);
        push(nodes, b);
    }

    int ans = 0;
    for (auto& node : nodes) {
        ans += dfs(node, 0);
    }

    cout << ans << endl;

    return 0;
}

这段代码首先定义了一个结构体 Node 来表示节点，并且提供了创建新节点的方法。然后，在主函数中读取输入并构造图。最后，通过深度优先搜索算法计算每个节点的预处理值，并输出结果。