拯救小P

题目描述

在一个 N×M （ 1 ≤ N, M ≤ 100 ）的迷宫里，小P被困在了迷宫的某个位置。迷宫由空地（用 0 表示）和墙壁（用 1 表示）组成。小P可以在1个单位时间内从当前位置移动到上下左右四个相邻的空地上。迷宫的左上角坐标为 (0, 0) ，右下角坐标为 (N - 1, M - 1) 。现在给出迷宫的布局以及小P的初始位置 (x, y) ，请你计算小P最少需要多少时间才能走出迷宫（走出迷宫的标志是到达迷宫的右下角）。如果小P无法走出迷宫，输出 -1 。

输入格式

第一行输入两个整数 N 和 M ，表示迷宫的行数和列数。 第二行输入两个整数 x 和 y ，表示小P的初始位置。 接下来 N 行，每行 M 个整数，每个整数为 0 或 1 ，表示迷宫的布局。

输出格式

输出一个整数，表示小P走出迷宫最少需要的时间，若无法走出迷宫，输出 -1 。

样例输入

5 5 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

样例输出

8

广度优先搜索算法解释：

广度优先搜索（Breadth - First Search，BFS）是一种用于图形数据结构（在C++ 中可以是图或者树等）的遍历算法。

基本原理

• 从给定的起始顶点开始，首先访问起始顶点，然后依次访问起始顶点的所有未访问邻接顶点，这些邻接顶点构成了第一层。接着，对第一层的每个顶点，访问它们未被访问的邻接顶点，这些顶点构成第二层，以此类推。就像以起始顶点为中心，一层一层地向外扩散访问顶点，直到所有可达顶点都被访问完。

实现方式

• 通常使用队列（ queue ）这种数据结构来辅助实现。把起始顶点放入队列，然后每次取出队首顶点，访问它的邻接顶点，并将未访问的邻接顶点放入队列，直到队列为空。
• 例如，假设有一个简单的迷宫（可以抽象为一个图），从起点开始寻找出口。把起点放入队列，然后取出起点，检查它上下左右能到达的点（未访问的空点），放入队列，接着不断从队列取出点进行相同操作，按照距离起点由近到远的顺序进行搜索，先找到出口就可以计算出最短路径长度（如果每步长度为1的话）。

时间复杂度

• 对于具有 V 个顶点和 E 个边的图，在最坏情况下，广度优先搜索的时间复杂度是 O(V + E)。因为每个顶点和边都可能被访问一次。

应用场景

• 主要用于寻找最短路径（在边权值相同的情况下）。例如在游戏地图中计算角色从一个点到另一个点的最短路线，在网络拓扑结构中查找两个节点之间的最短连接路径等；也用于图的连通分量的判断等