[LeetCode-695]最大岛屿面积
DFS 解法
class Solution:
dir = [(-1,0),(1,0),(0,-1),(0,1)]
def dfs(self,grid,x,y):
if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != 1:
return 0
grid[x][y] = 0
ans = 1
for (dx,dy) in self.dir:
ans += self.dfs(grid,x+dx,y+dy)
return ans
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
ans = max(ans, self.dfs(grid,i,j))
return ans[蓝桥杯]Python 数字三角形 DFS or 动态规划
题目的意思是向左走和向右走的结果的差值不能超过 1 过程中超过 1 是没有问题的
DFS 版本
这个版本会超时
n = int(input())
grid = [[0] * n] * n
for i in range(n):
grid[i] = list(map(int, input().strip().split()))
ret = 0
def dfs(x, y, max_val, balance_factor):
"""
:param x: 当前位置的横坐标
:param y: 当前位置的纵坐标
:param max_val: 上一层的最大值
:param balance_factor: 左转减去右转的次数
:return:
"""
if y > x:
return
global ret
if x == n - 1: # 到达最后一列
if abs(balance_factor) <= 1:
ret = max(ret, max_val)
return
dfs(x + 1, y, max_val + grid[x + 1][y], balance_factor + 1)
dfs(x + 1, y + 1, max_val + grid[x + 1][y + 1], balance_factor - 1)
dfs(0, 0, grid[0][0], 0)
print(ret)