|
3 | 3 | importjava.util.LinkedList; |
4 | 4 | importjava.util.Queue; |
5 | 5 |
|
6 | | -/** |
7 | | - * 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. |
8 | | -
|
9 | | - Given the ball's start position, the destination and the maze, determine whether the ball could stop at the destination. |
10 | | -
|
11 | | - 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. |
12 | | -
|
13 | | - Example 1 |
14 | | -
|
15 | | - Input 1: a maze represented by a 2D array |
16 | | -
|
17 | | - 0 0 1 0 0 |
18 | | - 0 0 0 0 0 |
19 | | - 0 0 0 1 0 |
20 | | - 1 1 0 1 1 |
21 | | - 0 0 0 0 0 |
22 | | -
|
23 | | - Input 2: start coordinate (rowStart, colStart) = (0, 4) |
24 | | - Input 3: destination coordinate (rowDest, colDest) = (4, 4) |
25 | | -
|
26 | | - Output: true |
27 | | - Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. |
28 | | -
|
29 | | - Example 2 |
30 | | -
|
31 | | - Input 1: a maze represented by a 2D array |
32 | | -
|
33 | | - 0 0 1 0 0 |
34 | | - 0 0 0 0 0 |
35 | | - 0 0 0 1 0 |
36 | | - 1 1 0 1 1 |
37 | | - 0 0 0 0 0 |
38 | | -
|
39 | | - Input 2: start coordinate (rowStart, colStart) = (0, 4) |
40 | | - Input 3: destination coordinate (rowDest, colDest) = (3, 2) |
41 | | -
|
42 | | - Output: false |
43 | | - Explanation: There is no way for the ball to stop at the destination. |
44 | | -
|
45 | | - Note: |
46 | | - There is only one ball and one destination in the maze. |
47 | | - Both the ball and the destination exist on an empty space, and they will not be at the same position initially. |
48 | | - The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls. |
49 | | - The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100. |
50 | | - */ |
51 | 6 | publicclass_490 { |
52 | 7 | /** |
53 | 8 | * BFS: the key part of this algorithm is that: this is a ball that won't stop rolling until it hits a wall. |
|