【BFS】穿越栅栏

题目

1374. 穿越栅栏

---

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

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

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

给定迷宫的宽度 $W$ 和高度 $H$ ，迷宫可以被看作一个方格矩阵。

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

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

已知，牛们只会沿着 $X$ 轴或 $Y$ 轴的方向移动，每一步只能从一个方格移动到另一个方格之中（走出迷宫，也算一步）。

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

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

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

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

输入格式

第一行包含两个整数 $W$ 和 $H$ 。

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

输出格式

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

数据范围

$1 \le W \le 38$ ，
$1 \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;
}