本文主要是介绍【USACO2.4.2】穿越栅栏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【问题描述】
FJ搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口，并且从迷宫中的任意一点都能找到一条走出迷宫的路。给定迷宫的宽 W 及长 H 和这个迷宫，然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的最少步数。
【输入格式】
第一行： W和H（用空格隔开）
第二行至第2*H+1行： 每行2*W+1个字符表示迷宫
【输出格式】
输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
【输入样例】
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
【输出样例】
9
算法:棋盘上的BFS(多源)
这个题输入有点恶心，给的不是一个正正规规的迷宫问题的迷宫而给的是迷宫的形状图,所以需要转化,把输入矩阵首行首列的坐标标号为0,那些横纵坐标为基数且自身为空格的点就是一个标准棋盘上的格子。
由于是墙障碍,设三元组a[x][y][4] 在=1时表示棋盘上点(x,y)的某个方向上有一堵墙。
又人为规定:
0: 西1: 北2: 东3: 南
再对原矩阵进行扫描标记，转化为普通的墙障碍问题,见【USACO2.4.2简单版本】
但要注意的是,由于没有给出具体的出口坐标,所以要用循环查找,但要注意特殊的点(四个角上的点不管一面无墙还是两面无墙都只存一次)
贴上代码
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 105
using namespace std;
int W,H;
struct node
{int x,y;
};
int dx[]={0,-1,0,1};
int dy[]={这篇关于【USACO2.4.2】穿越栅栏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
