栅栏迷宫
题目描述
田野上搭建了一个黄金大神专用的栅栏围成的迷宫. 幸运的是, 在迷宫的边界上留出了两段 栅栏作为迷宫的出口. 更幸运的是, 所建造的迷宫是一个 “完美的” 迷宫: 即你能从迷宫中的 任意一点找到一条走出迷宫的路. 给定迷宫的宽 W (1<=W<=38) 及长 H (1<=H<=100). 2H+1 行, 每行 2W+1 的字符以下面给出的格式表示一个迷宫. 然后计算从迷宫中最 “糟糕” 的那一个点走出迷宫所需的步数 (就是从最 “糟糕” 的一点, 走出迷宫的最少步数). (即使从这一点以最优的方式走向最靠近的出口, 它仍然需要最多的步数) 当然了, 黄金大神让你必须只会水平或垂直地在 X 或 Y 轴上移动, 你不能从来不走对角线. 每移动到一个新的方格算作一步 (包括移出迷宫的那一步) 这是一个 W=5, H=3 的迷宫:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+如上图的例子, 栅栏的柱子只出现在奇数行或奇数列. 每个迷宫只有两个出口.
输入格式
第一行: W 和 H (用空格隔开)
第二行至第 2H+1 行: 每行 2W+1 个字符表示迷宫
输出格式
输出一个单独的整数, 表示能保证牛从迷宫中任意一点走出迷宫的最小步数.
样例输入
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+样例输出
9提示
善良的学长: 样例输入可以复制进记事本或者文本文档这样看起来更加直观!! !=v=
Explanation
将数据读入, 然后考虑每一个格子周边的 - 和 | 两种字符, 来判断四连通性.
然后直接 BFS 一遍了事 (先处理出出口, 然后用 queue 维护等等).
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long lli;
const int maxn = 110;
int n, m;
char inp_dat[2 * maxn][2 * maxn];
bool access[maxn][maxn][4]; // Up, Right, Below, Left
int depth[maxn][maxn];
bool inque[maxn][maxn];
int main(int argc, char** argv)
{
scanf("%d%d", &m, &n);
string ___empty_str;
getline(cin, ___empty_str);
for (int i = 1; i <= 2 * n + 1; i++) {
string str;
getline(cin, str);
for (int j = 1; j <= 2 * m + 1; j++)
inp_dat[i][j] = str[j - 1];
}
// Post-scanning connections.
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
access[i][j][0] = inp_dat[2 * i - 1][2 * j] != '-';
access[i][j][1] = inp_dat[2 * i][2 * j + 1] != '|';
access[i][j][2] = inp_dat[2 * i + 1][2 * j] != '-';
access[i][j][3] = inp_dat[2 * i][2 * j - 1] != '|';
}
// Scanning exit
queue< pair<int, int> > que;
int exit_x = 0, exit_y = 0;
for (int i = 1; i <= n; i++) {
if (access[i][1][3]) {
exit_x = 1, exit_y = i;
que.push( make_pair(exit_y, exit_x) );
inque[exit_y][exit_x] = true;
depth[exit_y][exit_x] = 1;
}
else if (access[i][m][1]) {
exit_x = m, exit_y = i;
que.push( make_pair(exit_y, exit_x) );
inque[exit_y][exit_x] = true;
depth[exit_y][exit_x] = 1;
}
}
for (int j = 1; j <= m; j++) {
if (access[1][j][0]) {
exit_x = j, exit_y = 1;
que.push( make_pair(exit_y, exit_x) );
inque[exit_y][exit_x] = true;
depth[exit_y][exit_x] = 1;
}
else if (access[n][j][2]) {
exit_x = j, exit_y = n;
que.push( make_pair(exit_y, exit_x) );
inque[exit_y][exit_x] = true;
depth[exit_y][exit_x] = 1;
}
}
// Discovered exit, deep searching.
while (!que.empty()) {
pair<int, int> pr = que.front();
int px = pr.second, py = pr.first;
// printf("enque %d %d depth %d\n", px, py, depth[py][px]);
que.pop();
if (px < 1 || px > m || py < 1 || py > n)
continue;
if (access[py][px][0] && (depth[py - 1][px] == 0 || depth[py - 1][px] > depth[py][px] + 1)) {
depth[py - 1][px] = depth[py][px] + 1;
if (!inque[py - 1][px]) {
que.push( make_pair(py - 1, px) );
inque[py - 1][px] = true;
}
}
if (access[py][px][1] && (depth[py][px + 1] == 0 || depth[py][px + 1] > depth[py][px] + 1)) {
depth[py][px + 1] = depth[py][px] + 1;
if (!inque[py][px + 1]) {
que.push( make_pair(py, px + 1) );
inque[py][px + 1] = true;
}
}
if (access[py][px][2] && (depth[py + 1][px] == 0 || depth[py + 1][px] > depth[py][px] + 1)) {
depth[py + 1][px] = depth[py][px] + 1;
if (!inque[py + 1][px]) {
que.push( make_pair(py + 1, px) );
inque[py + 1][px] = true;
}
}
if (access[py][px][3] && (depth[py][px - 1] == 0 || depth[py][px - 1] > depth[py][px] + 1)) {
depth[py][px - 1] = depth[py][px] + 1;
if (!inque[py][px - 1]) {
que.push( make_pair(py, px - 1) );
inque[py][px - 1] = true;
}
}
inque[py][px] = false;
}
// Discovering farthest node
int max_dist = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
max_dist = max(max_dist, depth[i][j]);
printf("%d\n", max_dist);
return 0;
}