※ 引述《DJYOSHITAKA (franchouchouISBEST)》之銘言：
: 原本想要寫第二題
: 被你版系列文搞到:(
: py好難
: 我一定有一堆地方寫的有問題
: 懶得檢查 對不起
: def dfs(self, i, j, cur, cur_max, grid: List[List[int]]) -> int:
: if self.visit[i][j] == 1 or grid[i][j] == 0:
: return cur
: m = len(grid)
: n = len(grid[0])
: self.visit[i][j] = 1
: cur += grid[i][j]
: if i-1 >= 0:
: cur_max = max(cur_max, self.dfs(i-1, j, cur, cur_max, grid))
: if i+1 < m:
: cur_max = max(cur_max, self.dfs(i+1, j, cur, cur_max, grid))
: if j-1 >= 0:
: cur_max = max(cur_max, self.dfs(i, j-1, cur, cur_max, grid))
: if j+1 < n:
: cur_max = max(cur_max, self.dfs(i, j+1, cur, cur_max, grid))
: self.visit[i][j] = 0
: return cur_max
: def getMaximumGold(self, grid: List[List[int]]) -> int:
: ans = 0
: for i in range(len(grid)):
: for j in range(len(grid[0])):
: self.visit = [[0]*len(grid[0]) for i in range(len(grid))]
: ans = max(ans, self.dfs(i, j, 0, 0, grid))
: return ans
思路:
經典DFS
Python Code:
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
max_res = 0
def dfs(grid,visited,x,y):
visited.add((x,y))
if grid[y][x] == 0:
return 0
else:
res = grid[y][x]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for i in range(4):
new_x = x+dx[i]
new_y = y+dy[i]
if new_x>=0 and new_x<m and new_y>=0 and new_y<n:
if grid[new_y][new_x] !=0 and (new_x,new_y) not in
visited:
res =
max(dfs(grid,visited,new_x,new_y)+grid[y][x],res)
visited.remove((x,y))
return res
for i in range(n):
for j in range(m):
max_res = max(dfs(grid,set(),j,i),max_res)
return max_res
晚安捏