給出一個(gè)m行n列迷宮圖，從最上排開始丟小球，輸出list型answer，answer[i]表示從最下排i槽掉下的是最上端第answer[i]個(gè)槽的小球
例如：
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]]
表示下圖
\\\//
\\\//
///\\
\\\\/
/////
從最上排最左側(cè)的球會在最下排第二個(gè)槽落出
兩種思路：
思路一：對最上排每個(gè)槽DFS，估計(jì)Memory使用會比較高
思路二：開兩個(gè)數(shù)組dp和dp_pre，dp[j]表示下一行第i槽的球來自初始第一行第dp[j]個(gè)槽，dp_pre存當(dāng)前行的結(jié)果。初始化dp全-1，dp_pre為0-n-1
如果當(dāng)前行第j個(gè)格子是'\'，那么必須滿足1.不是最右邊一個(gè)槽，2.該槽右邊的槽也是'\'，那么小球落入下一行j+1個(gè)槽位
如果當(dāng)前行第j個(gè)格子是'/'，那么必須滿足1.不是最左邊一個(gè)槽，2.該槽右邊的槽也是'/'，那么小球落入下一行j-1個(gè)槽位
復(fù)雜度O(m*n)
Memory使用量很優(yōu)秀~
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