请求c++版std代码

Question

旗帜(flag)
题目背景
在二战时期，著名的美国上将麦克阿瑟让手下突击前往敌军司令部，目的将敌方的司令部炸毁，这将对美国对战争的胜利有很大的帮助。就在手下商议突击计划时，电报员突然来信，说地方开始集体撤退，同时疑似监听到敌方准备了大量的导弹，准备对我军阵地轰炸，现已监听到了每个时刻轰炸的地点，轰炸过的地方将会有大量残骸，不好通行；正在轰炸的地方去了又会死伤惨重。局势一下子紧张了起来，麦克阿瑟也皱紧了眉头。突然，麦克阿瑟想到了身为计算机专家的你，他希望你能够帮助求出一个能够快速通行的路线

题目描述
现已知当前阵地的长和宽、我方司令部与敌方司令部的坐标以及阵地的情况，其中每个地块用空格隔开的数字 $0$ 或 $1$ 表示当前地块是否堆积了大量的残骸，无法通行。若为 $0$ ，即视为可以通行，否则视为不可通行。同时给出监听到 $n$ 组轰炸数据与每组数据中江北轰炸的地块的坐标。

求从我方司令部到敌方司令部所需的最短时间。

输入格式
第 $1$ 行给出 $h$ , $w$，表示当前阵地的长和宽。

第 $2$ 行至第 $1+h$ 给出阵地，其中每个地块 $a_{i,j}$ 用数字 $0$ 或 $1$ 表示当前地块是否堆积了大量的残骸，无法通行。若为 $0$ ，即视为可以通行，否则视为不可通行。

第 $2+h$ 行给出监听到 $n$ 组轰炸数据。

后 $n$ 段每段第一行给出一个数 $s$，表示在当前时间刻度有 $s$ 个坐标为 $(x_i,y_i)$ 的地块将开始轰炸（坐标可能会重复）。

最后一行给出我方司令部与敌方司令部的坐标。

输出格式
一行，表示我方司令部到敌方司令部所需的最短时间，如果不能到达，输出 $-1$ 。

提示
$1 \le h \le w \le 10^4$

$1 \le s \le 100$

$1 \le x_i \le h$

$1 \le y_i \le w$

保证 $a_{-th,-th}$ 一定为 $0$ 或者 $1$

Answer 1

🕒上午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：“生活就像骑自行车。要保持平衡，就得不断前进。” — 阿尔伯特·爱因斯坦

为了求解这个问题，我们可以使用广度优先搜索（BFS）算法来找到从我方司令部到敌方司令部的最短路径。我们需要考虑到炸弹的影响，炸弹会在特定的时间刻度内使某些地块变为不可通行。

以下是一个 C++ 的实现代码，包含了输入处理、BFS 搜索以及炸弹影响的处理：

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>

using namespace std;

const int MAX_H = 10000;
const int MAX_W = 10000;
const int DIRECTIONS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 下，上，右，左

int h, w;
int grid[MAX_H][MAX_W]; // 地块状态
bool bombed[MAX_H][MAX_W]; // 记录被轰炸的地块
vector<vector<int>> bomb_schedule; // 轰炸时间表

bool is_valid(int x, int y) {
    return x >= 0 && x < h && y >= 0 && y < w && grid[x][y] == 0;
}

int bfs(int start_x, int start_y, int end_x, int end_y) {
    queue<tuple<int, int, int>> q; // (x, y, time)
    q.push(make_tuple(start_x, start_y, 0));
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    visited[start_x][start_y] = true;

    while (!q.empty()) {
        auto [x, y, time] = q.front();
        q.pop();

        // 如果到达敌方司令部
        if (x == end_x && y == end_y) {
            return time;
        }

        // 检查当前时间是否有轰炸
        if (time < bomb_schedule.size()) {
            for (auto &bomb : bomb_schedule[time]) {
                bombed[bomb.first][bomb.second] = true;
            }
        }

        // 尝试四个方向
        for (auto &dir : DIRECTIONS) {
            int new_x = x + dir[0];
            int new_y = y + dir[1];

            if (is_valid(new_x, new_y) && !bombed[new_x][new_y] && !visited[new_x][new_y]) {
                visited[new_x][new_y] = true;
                q.push(make_tuple(new_x, new_y, time + 1));
            }
        }

        // 轰炸结束，恢复状态
        if (time < bomb_schedule.size()) {
            for (auto &bomb : bomb_schedule[time]) {
                bombed[bomb.first][bomb.second] = false;
            }
        }
    }

    return -1; // 无法到达
}

int main() {
    cin >> h >> w;

    // 读取阵地状态
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
        }
    }

    // 读取轰炸数据
    int n;
    cin >> n;
    bomb_schedule.resize(n);
    for (int i = 0; i < n; ++i) {
        int s;
        cin >> s;
        bomb_schedule[i].resize(s);
        for (int j = 0; j < s; ++j) {
            int x, y;
            cin >> x >> y;
            bomb_schedule[i][j] = {x - 1, y - 1}; // 转换为0-indexed
        }
    }

    // 读取司令部坐标
    int start_x, start_y, end_x, end_y;
    cin >> start_x >> start_y >> end_x >> end_y;
    start_x--; start_y--; end_x--; end_y--; // 转换为0-indexed

    // 进行BFS搜索
    int result = bfs(start_x, start_y, end_x, end_y);
    cout << result << endl;

    return 0;
}

代码说明：

1. 输入处理：

   • 读取阵地的长和宽。
   • 读取阵地的状态（0表示可通行，1表示不可通行）。
   • 读取轰炸数据，存储在 bomb_schedule 中。
   • 读取我方和敌方司令部的坐标。

2. BFS搜索：

   • 使用队列进行广度优先搜索，记录当前的位置和时间。
   • 在每个时间刻度检查是否有轰炸，并更新 bombed 数组。
   • 尝试四个方向移动，如果可以通行且未被访问，则加入队列。
   • 如果到达敌方司令部，返回所需的时间。

3. 输出结果：

   • 如果找到路径，输出所需的时间；如果无法到达，输出 -1。

注意事项：

• 代码中使用了 0-indexed 的坐标，因此在读取输入时进行了转换。
• 由于可能存在大量的地块和轰炸数据，确保使用合适的数据结构以提高效率。