There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up , down , left or right , but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position , the destination and the maze , determine whether the ball could stop at the destination.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
Example 1:
Input 1: a maze represented by a 2D array 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 Input 2: start coordinate (rowStart, colStart) = (0, 4) Input 3: destination coordinate (rowDest, colDest) = (4, 4) Output: true Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Example 2:
Input 1: a maze represented by a 2D array 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 Input 2: start coordinate (rowStart, colStart) = (0, 4) Input 3: destination coordinate (rowDest, colDest) = (3, 2) Output: false Explanation: There is no way for the ball to stop at the destination.
Note:
由空地和墙组成的迷宫中有一个**球**。球可以向**上下左右**四个方向滚动,但在遇到墙壁前不会停止滚动。当球停下时,可以选择下一个方向。
给定球的**起始位置**,目的地**和**迷宫,判断球能否在目的地停下。
迷宫由一个**0**和**1**的二维数组表示。 **1**表示墙壁,**0**表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4) 输入 3: 目的地坐标 (rowDest, colDest) = (4, 4) 输出: true 解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。
示例 2:
输入 1: 迷宫由以下二维数组表示 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4) 输入 3: 目的地坐标 (rowDest, colDest) = (3, 2) 输出: false 解析: 没有能够使球停在目的地的路径。
注意:
2
块空地,行数和列数均不超过100
。