9月30日上午，科学摸鱼，摸到了一道深搜的题，卧槽，真尼玛摸出来了。
2658. 网格图中鱼的最大数目
给你一个下标从 0开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示：
如果 grid[r][c] = 0，那么它是一块陆地 。
如果 grid[r][c] > 0 ，那么它是一块水域 ，且包含 grid[r][c]条鱼。
一位渔夫可以从任意 水域格子 (r, c)出发，然后执行以下操作任意次：
捕捞格子(r, c)处所有的鱼，或者移动到相邻的水域格子。
请你返回渔夫最优策略下，最多可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。
格子 (r, c)相邻的格子为 (r, c + 1)，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相邻格子在网格图内。
示例 1：
输入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输出：7
解释：渔夫可以从格子 (1,3)出发，捕捞 3 条鱼，然后移动到格子 (2,3)，捕捞 4 条鱼。
示例 2：
输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
输出：1
解释：渔夫可以从格子 (0,0) 或者 (3,3) ，捕捞 1 条鱼。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10
一顿乱咔咔，tab键设置的是4个空格，有强迫症的就不看了。
# @param {Integer[][]} grid
# @return {Integer}
def find_max_fish(grid)
ans = -1.0/0.0
len1 = grid.length
len2 = grid[0].length
for i in 0...len1
for j in 0...len2
if grid[i][j] > 0
@h = {}
@h[[i,j]] = 1
@cnt = grid[i][j]
dfs(i,j,len1,len2,grid)
ans = [ans,@cnt].max
end
end
end
if ans.to_f.infinite? == -1
return 0
else
return ans
end
end
def dfs(x,y,len1,len2,grid)
if [[0,1],[0,-1],[1,0],[-1,0]].all? {|x1,y1| x1+x < 0 || x1+x >= len1 || y1+y < 0 || y1+y >= len2 || grid[x+x1][y+y1] == 0 || @h.key?([x+x1,y+y1])}
return @cnt
else
for (x1,y1) in [[0,1],[0,-1],[1,0],[-1,0]]
if x1+x >= 0 && x1+x < len1 && y1+y >= 0 && y1+y < len2 && grid[x+x1][y+y1] > 0 && (!@h.key?([x+x1,y+y1]))
@cnt += grid[x+x1][y+y1]
@h[[x+x1,y+y1]] = 1
dfs(x+x1,y+y1,len1,len2,grid)
end
end
end
end
