请给出【18NOIP普及组】摆渡车的解题思路以及实现代码

【18NOIP普及组】摆渡车是一道经典的模拟题，可以通过模拟车辆在两个岸边的运动来求解。下面是解题思路与实现代码：

1. 首先，我们需要定义一个结构体来表示车辆的状态，包括位置、时间和方向：

struct Status {
    int pos, time;
    bool dir; // true表示从左到右，false表示从右到左
};

2. 接下来，我们需要定义一个队列来保存车辆的状态。初始化时，将车辆从左岸开始，状态设置为{0, 0, true}，即在左岸位置为0，时间为0，方向为从左到右。将这个状态入队。

queue<Status> q;
q.push({0, 0, true});

3. 接下来，我们需要进行 BFS 搜索。每次从队列中取出一个状态 s，然后考虑所有可能的转移情况：

- 从左岸到右岸：如果当前方向为从左到右，且当前位置在左岸，那么可以考虑从左岸到右岸的转移。需要判断右岸是否有空位，并且需要考虑当前时间是否晚于所有等待在右岸的车辆到达的时间。如果可以转移，那么将转移后的状态插入队列中。
- 从右岸到左岸：如果当前方向为从右到左，且当前位置在右岸，那么可以考虑从右岸到左岸的转移。需要判断左岸是否有空位，并且需要考虑当前时间是否晚于所有等待在左岸的车辆到达的时间。如果可以转移，那么将转移后的状态插入队列中。
- 没有转移：如果当前状态无法进行任何转移，那么就将其弹出队列。

while (!q.empty()) {
    Status s = q.front(); q.pop();

    // 左岸到右岸
    if (s.dir && s.pos < n && (s.time < arrive_right[s.pos] || right.empty())) {
        Status t{s.pos + 1, s.time + t_left_right, s.dir ^ 1};
        if (visited.find(t) == visited.end()) {
            visited.insert(t);
            q.push(t);
        }
    }

    // 右岸到左岸
    if (!s.dir && s.pos > 0 && (s.time < arrive_left[s.pos - 1] || left.empty())) {
        Status t{s.pos - 1, s.time + t_right_left, s.dir ^ 1};
        if (visited.find(t) == visited.end()) {
            visited.insert(t);
            q.push(t);
        }
    }

    // 无法转移
    if (!s.dir && s.pos == 0) {
        ans = s.time;
        break;
    }
}

4. 最后，我们可以在 BFS 过程中维护一个 visited 集合来避免重复搜索。当车辆到达右岸且无法进行任何转移时，即可得到最终答案。

完整代码如下：