题目描述
农夫约翰发疯了,居然在田野中建造了一个巨大的用栅栏搭成的迷宫。
所幸的是,迷宫的边缘有两处栏杆处于空缺状态,也就是说迷宫有两个出口。
而这个迷宫也设计的非常完美,从任何位置出发,都能够找到迷宫的出路。
给定迷宫的宽度 $W$ 和高度 $H$,迷宫可以被看作一个方格矩阵。
我们可以用一个 $2×H+1$ 行,每行 $2×W+1$ 个字符的矩阵来描绘整个迷宫,具体形式可参考下面的示例。
我们现在要在迷宫中找到最糟糕的位置,最糟糕的位置是指一头奶牛从某地出发,以最优的方式走向距离该地最近的出口,走出迷宫所需行走步数最多的地点。
已知,牛们只会沿着 $X$ 轴或 $Y$ 轴的方向移动,每一步只能从一个方格移动到另一个方格之中(走出迷宫,也算一步)。
下面是一个 $W=5,H=3$ 的迷宫:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
栅栏柱只出现在奇数行和奇数列中,每个迷宫的边缘都有两个出口。
请问,一头牛从最糟糕点出发,走出迷宫最少要用多少步。
输入格式
第一行包含两个整数 $W$ 和 $H$。
接下来 $2×H+1$ 行,每行 $2×W+1$ 个字符,用来描述迷宫。
输出格式
输出一个整数,表示从最糟糕点出发,走出迷宫所需的最少步数。
数据范围
$1≤W≤38$
$1≤H≤100$
输入样例
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
输出样例
9
BFS
一开始做这一题的时候,是枚举每一个空格点,BFS 一遍,发现 TLE 了,只过了 $7$ 个测试点。
然后采用从每个出口向内 BFS,就过了,因为是线性的,BFS 也仅仅只走两遍。
$dist$ 初始化为 $0x3f3f3f3f$ 和 $-1$ 都可以,因为每个空格位置都是可达出口的,但是如果某些点不可达,就只能初始化为 $-1$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 210, M = 100;
int n, m;
int dist[2][N][M];
string mp[N];
struct point {
int x, y;
};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool check(int x, int y, int d)
{
return mp[2 * x - 1 + dx[d]][2 * y - 1 + dy[d]] == ' ';
}
void bfs(int sx, int sy, int dist[][M])
{
memset(dist, -1, N * M * 4); // 4 个字节
queue <point> q;
q.push({sx, sy});
dist[sx][sy] = 1;
while (!q.empty()) {
point now = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int x = now.x + dx[i];
int y = now.y + dy[i];
if (x < 1 || x > n || y < 1 || y > m) continue;
if (!check(now.x, now.y, i)) continue;
if (dist[x][y] == -1) {
dist[x][y] = dist[now.x][now.y] + 1;
q.push({x, y});
}
}
}
}
int main()
{
cin >> m >> n;
getchar();
for (int i = 0; i < 2 * n + 1; ++i) {
getline(cin, mp[i]);
}
int k = 0;
// 枚举左右边界
for (int i = 1; i <= n; ++i) {
if (check(i, 1, 3)) bfs(i, 1, dist[k++]);
if (check(i, m, 1)) bfs(i, m, dist[k++]);
}
// 枚举上下边界
for (int i = 1; i <= m; ++i) {
if (check(1, i, 0)) bfs(1, i, dist[k++]);
if (check(n, i, 2)) bfs(n, i, dist[k++]);
}
int res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
res = max(res, min(dist[0][i][j], dist[1][i][j]));
}
}
cout << res << endl;
return 0;
}