侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【BFS】穿越栅栏

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 279 阅读 / 910 字
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1374. 穿越栅栏


农夫约翰发疯了,居然在田野中建造了一个巨大的用栅栏搭成的迷宫。

所幸的是,迷宫的边缘有两处栏杆处于空缺状态,也就是说迷宫有两个出口。

而这个迷宫也设计的非常完美,从任何位置出发,都能够找到迷宫的出路。

给定迷宫的宽度 WW 和高度 HH ,迷宫可以被看作一个方格矩阵。

我们可以用一个 2×H+12 \times H + 1 行,每行 2×W+12 \times W + 1 个字符的矩阵来描绘整个迷宫,具体形式可参考下面的示例。

我们现在要在迷宫中找到最糟糕的位置,最糟糕的位置是指一头奶牛从某地出发,以最优的方式走向距离该地最近的出口,走出迷宫所需行走步数最多的地点。

已知,牛们只会沿着 XX 轴或 YY 轴的方向移动,每一步只能从一个方格移动到另一个方格之中(走出迷宫,也算一步)。

下面是一个 W=5,H=3W = 5,H = 3 的迷宫:

+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

栅栏柱只出现在奇数行和奇数列中,每个迷宫的边缘都有两个出口。

请问,一头牛从最糟糕点出发,走出迷宫最少要用多少步。

输入格式

第一行包含两个整数 WWHH

接下来 2×H+12 \times H + 1 行,每行 2×W+12 \times W + 1 个字符,用来描述迷宫。

输出格式

输出一个整数,表示从最糟糕点出发,走出迷宫所需的最少步数。

数据范围

1W381 \le W \le 38
1H1001 \le H \le 100

输入样例:

5 3
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

输出样例:

9

解题

方法一:BFS

思路

找到两个出口,从两个出口同时开始宽搜,并记录步数,直到走完整个迷宫的步数即为从最糟糕点出发,走出迷宫所需的最少步数。

代码

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

using namespace std;

typedef pair<int, int> PII;

const int W = 40, H = 110, DIRS[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int w, h, ww, hh;
char g[H * 2][W * 2];
bool vis[H][W];
int ans = 0x3f3f3f3f;
vector<PII> vec;

bool access(int x, int y, int dir) {
    return g[x * 2 + 1 + DIRS[dir][0]][y * 2 + 1 + DIRS[dir][1]] == ' ';
}

void bfs() {
    queue<PII> que;
    for (auto& pr : vec) {
        int x = pr.first, y = pr.second;
        que.push({x, y});
        vis[x][y] = true;
    }
    int step = 0;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            auto pr = que.front();
            que.pop();
            int x = pr.first, y = pr.second;
            for (int i = 0; i < 4; ++i) {
                if (!access(x, y, i)) continue;
                int nx = x + DIRS[i][0], ny = y + DIRS[i][1];
                if (nx >= 0 && nx < h && ny >= 0 && ny < w && !vis[nx][ny]) {
                    que.push({nx, ny});
                    vis[nx][ny] = true;
                }
            }
        }
        ++step;
    }
    ans = min(ans, step);
}

int main() {
    scanf("%d%d", &w, &h);
    ww = w * 2 + 1, hh = h * 2 + 1;
    for (int i = 0; i < hh; ++i) {
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        for (int j = 0; j < ww; ++j) scanf("%c", &g[i][j]);
    }
    for (int i = 0; i < h; ++i) {
        if (access(i, 0, 3)) vec.push_back({i, 0});
        if (access(i, w - 1, 1)) vec.push_back({i, w - 1});
    }
    for (int i = 0; i < w; ++i) {
        if (access(0, i, 0)) vec.push_back({0, i});
        if (access(h - 1, i, 2)) vec.push_back({h - 1, i});
    }
    bfs();
    printf("%d\n", ans);
    
    return 0;
}
0

评论区