题目链接：1706. 球会落何处
模拟即可。
当小球下方的挡板方向向左，那其下方左侧的挡板也向左；或者小球下方的挡板方向向右，且其下方右侧的挡板方向也向右，小球才能落到下一行。
Note: 因为最终的下落结果只和小球的位置有关，因此可以使用这个特点记录历史结果，节约计算次数。但是实际测试，这种方式并不能提高速度，甚至会更慢。可能是缓存命中率比较低。
from typing import List
class Solution:
# def __init__(self):
# self.cache = dict()
def fall(self, pos: int, grid: List[List[int]]) -> int:
if len(grid) == 0 or pos == -1:
return pos
m, n = len(grid), len(grid[0])
# if (pos, m) in self.cache:
# return self.cache.get((pos, m))
if not (0 <= pos + grid[0][pos] < n) or grid[0][pos + grid[0][pos]] != grid[0][pos]:
res = -1
else:
res = self.fall(pos + grid[0][pos], grid[1:])
# self.cache[(pos, m)] = res
return res
def findBall(self, grid: List[List[int]]) -> List[int]:
m = len(grid)
if m == 0:
return []
n = len(grid[0])
if n == 0 or n == 1:
return [-1] * n
return [self.fall(i, grid) for i in range(n)]