the_maze.md

The Maze

定义:

determine whether the ball could stop at the destination.

这里对于stop的判定条件是：球从一个方向朝着end卷过来，能否在end点的下一个位置碰到墙。举个不成立的例子

比如你从左边冲过来，到达了end，虽然end点的上下两头都有墙，但右边没有墙，这种就不符合定义。

思路

有了定义的条件，不难想象这是一道图的遍历。DFS和BFS都行。这里说一下BFS的思路。

BFS前的基础设施

1. 放入Queue的条件：当满足没有被访问过，且是一个新的起始点，我们放入Queue。新的起始点的定义是：从任意方向撞过来，并且触碰到墙后，触碰墙之前的最后一个节点。
2. 访问数组设立有个和input matrix等长宽的二维boolean数组

根据题目尿性的额外设施

1. 方向数组，这个如果不写也行，只是要多写几个方向的判断。写的话，写成上下左右四个方向比较顺溜。

BFS主代码

和一般的BFS没什么区别，先把最开始的起始点从Queue中pop出来，比对Termination Condition(是否和终结点坐标一致)。

不一致的话，就开始上下左右四个方向的滚动，每次滚动都滚到底，之后记住要回撤一部，因为while的终止条件使得最后球的坐标会在一面墙上。然后对回撤完了的这个节点进行去重比较，没Visited过就放入queue中，成为之后上下左右滚动的起始点

代码

Time: O(m * n): worst case visit the entire matrix Space: O(m * n): Visited Matrix

from collections import deque

class Solution(object):
    def hasPath(self, matrix, start, end):
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]  # up down left right
        visited = [[False] * len(matrix[0]) for _ in range(len(matrix))]
        visited[start[0]][start[1]] = True

        q = deque([start])

        while q:
            tup = q.popleft()
            if tup[0] == end[0] and tup[1] == end[1]:
                return True

            for dir in dirs:
                # Roll the ball until it hits a wall
                row = tup[0] + dir[0]
                col = tup[1] + dir[1]

                while 0 <= row < len(matrix) and 0 <= col < len(matrix[0]) and matrix[row][col] == 0:
                    row += dir[0]
                    col += dir[1]

                # x and y locates @ a wall when exiting the above while loop, so we need to backtrack 1 position
                (new_x, new_y) = (row - dir[0], col - dir[1])

                # Check if the new starting position has been visited
                if not visited[new_x][new_y]:
                    q.append((new_x, new_y))
                    visited[new_x][new_y] = True
        return False