The Maze
There is aballin a maze with empty spaces and walls. The ball can go through empty spaces by rollingup,down,leftorright, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball'sstart position, thedestinationand themaze, 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:
- There is only one ball and one destination in the maze.
- Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
- 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.
- The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
Solution:
It's a implicit graph search problem. Basically a disguised BFS problem.
Use BFS, a queue and a set. to store possible next steps, and record visited coordinates.
A helper function getNextMoves() to find possible next moves.
Time complexity: O(V+E)
Code:
class Solution(object):
def hasPath(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: bool
"""
visited = set()
frontier = [start]
while frontier:
nextF = []
for [row, col] in frontier:
if [row, col] == destination:
return True
visited.add((row,col)) # when you leave current position, it becomes visited
moves = self.getNextMoves(maze, [row,col], visited)
nextF.extend(moves)
frontier = nextF
# here it means you have exhaust all possible moves and not finding destination
return False
# return the possible next moves in a list, it could return length 0 upto length 4
def getNextMoves(self, maze, start, visited):
res = []
rowNum = len(maze)
colNum = len(maze[0])
# roll ball down
row, col = start
while row < rowNum and maze[row][col] != 1:
row += 1
# it means we go beyond wall or we hit a wall
# and (row == rowNum or maze[row][col] == 1): # I dont think we need the second half of the check()
if [row-1,col] != start and (row-1,col) not in visited:
res.append([row-1, col])
# roll ball up
row, col = start
while row >= 0 and maze[row][col] != 1:
row -= 1
if [row+1,col] != start and (row+1,col) not in visited:
res.append([row+1, col])
# roll ball left
row, col = start
while col >= 0 and maze[row][col] != 1:
col -= 1
if [row, col+1] != start and (row,col+1) not in visited:
res.append([row, col + 1])
# roll ball right
row, col = start
while col < colNum and maze[row][col] != 1:
col += 1
if [row, col-1] != start and (row,col-1) not in visited:
res.append([row, col - 1])
return res