给出一个m行n列迷宫图，从最上排开始丢小球，输出list型answer，answer[i]表示从最下排i槽掉下的是最上端第answer[i]个槽的小球
例如：
grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
表示下图
\\\//
\\\//
///\\
\\\\/
/////
从最上排最左侧的球会在最下排第二个槽落出
两种思路：
思路一：对最上排每个槽DFS，估计Memory使用会比较高
思路二：开两个数组dp和dp_pre，dp[j]表示下一行第i槽的球来自初始第一行第dp[j]个槽，dp_pre存当前行的结果。初始化dp全-1，dp_pre为0-n-1
如果当前行第j个格子是'\'，那么必须满足1.不是最右边一个槽，2.该槽右边的槽也是'\'，那么小球落入下一行j+1个槽位
如果当前行第j个格子是'/'，那么必须满足1.不是最左边一个槽，2.该槽右边的槽也是'/'，那么小球落入下一行j-1个槽位
复杂度O(m*n)
Memory使用量很优秀~
Runtime: 238 ms, faster than 78.93% of Python online submissions for Where Will the Ball Fall.
Memory Usage: 13.4 MB, less than 100.00% of Python online submissions for Where Will the Ball Fall.
1 #1706
2 #Runtime: 238 ms
3 #Memory Usage: 13.4 MB
4
5 class Solution(object):
6 def findBall(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: List[int]
10 """
11 dp = [-1] * len(grid[0])
12 dp_pre = range(len(grid[0]))
13 for i in range(len(grid)):
14 for j in range(len(grid[0])):
15 if grid[i][j] == 1:
16 if j < len(grid[0]) - 1 and grid[i][j + 1] == 1:
17 dp[j + 1] = dp_pre[j]
18 if grid[i][j] == -1:
19 if j > 0 and grid[i][j - 1] == -1:
20 dp[j - 1] = dp_pre[j]
21 dp_pre = dp
22 dp = [-1] * len(grid[0])
23 dp = [-1] * len(grid[0])
24 for i in range(len(dp)):
25 if dp_pre[i] != -1:
26 dp[dp_pre[i]] = i
27 return dp