一道都说好的BFS题目，细节多，码风飒：CF1638D Big Brush

小码匠

发布于 2024-04-11 09:10:55

1320

发布于 2024-04-11 09:10:55

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

昨天晚上到家后，刷完一道题后，老码农让那我看

CF1638D Big Brush

当时想了一会，有思路，无奈都11点了，本女生眼都睁不开了，直接睡觉了。

今天晚上回来后，老码农本来又想让我继续做CF1638D Big Brush这道题，

我看浏览器打开着：P1126 机器人搬重物，就毫不留情抛弃了：CF1638D Big Brush。

又被坑了，莫非又是老码农故意挖的坑。

题目地址：https://www.luogu.com.cn/problem/P1126

这道题一眼就是典型的BFS，无奈细节很多，调了很长时间，最终喜获80分，居然还被老码农表扬了。

正当我想溜的时候，老码农提示了我一句，好像还有个-1的分支。

呜呼哀哉，题目又没看清，丢掉了`如果无法到达，输出 ?1。

火速修改代码，自然是AC掉了。

题目的思路就分享了，分享我的代码吧。

借用老码农的原话：俺家娃的码风非常爽，喜欢，有我的风范。

说了半天，变相还是在夸自己，人上了岁数，脸皮就不能薄点吗？

好啦，我困啦，闪了。

最后分享我的代码

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_NUM = 5e1 + 5;

int sx[3] = {1, 2, 3};
int sy[3] = {1, 2, 3};
int way_x[4] = {0, 1, 0, -1};
int way_y[4] = {1, 0, -1, 0};
int n, m;
int ans[MAX_NUM][MAX_NUM];
bool vis[MAX_NUM][MAX_NUM], thing[MAX_NUM][MAX_NUM];

struct pos {
    int x, y, way;
};

int turn(int a, int b) {
    if (a == b) {
        return  0;
    }
    if (abs(a - b) == 2) {
        return  2;
    } else {
        return  1;
    }
}

void bfs(pos start) {
    queue<pos> q;
    q.push(start);
    vis[start.x][start.y] = true;
    while (!q.empty()) {
        auto fa = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 3; ++j) {
                pos son;
                son.x = fa.x + sx[j] * way_x[i];
                son.y = fa.y + sy[j] * way_y[i];
                son.way = i;

                if (thing[son.x][son.y]) {
                    break;
                }

                int value = ans[fa.x][fa.y] + 1 + turn(son.way, fa.way);
                if (son.x < 1 || son.x >= n 
                        || son.y < 1 || son.y >= m 
                        || value > ans[son.x][son.y]) {
                    continue;
                }

                ans[son.x][son.y] = value;
                q.push(son);
                vis[son.x][son.y] = true;
            }
        }
    }
}

void best_coder() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            if (x == 1) {
                thing[i][j] = true;
                thing[i + 1][j] = true;
                thing[i][j + 1] = true;
                thing[i + 1][j + 1] = true;
            }
            ans[i][j] = 0x7f7f7f;
        }
    }

    pos start, last;
    char w;
    cin >> start.x >> start.y >> last.x >> last.y >> w;
    if (w == 'E') {
        start.way = 0;
    } else if (w == 'S') {
        start.way = 1;
    } else if (w == 'W') {
        start.way = 2;
    } else {
        start.way = 3;
    }

    ans[start.x][start.y] = 0;

    bfs(start);

    if (ans[last.x][last.y] == 0x7f7f7f) {
        cout << -1;
        return;
    }
    cout << ans[last.x][last.y];
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

本文参与?腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-04-11，如有侵权请联系?cloudcommunity@tencent.com 删除

机器人