杭州建设工程信息网站,怎么制作个人作品网站,旅游景点网站建设,wordpress密码看文章文章目录 DFS滑行#xff08;DFS 记忆搜索#xff09; 思路#xff1a; 要思考回溯怎么写#xff08;入参与返回值、递归到哪里#xff0c;递归的边界和入口#xff09; DFS
滑行#xff08;DFS 记忆搜索#xff09; 代码分析#xff1a; 学会将输入的数据用二维列表… 文章目录 DFS滑行DFS 记忆搜索 思路 要思考回溯怎么写入参与返回值、递归到哪里递归的边界和入口 DFS
滑行DFS 记忆搜索 代码分析 学会将输入的数据用二维列表保存对于递归函数的输入就用 坐标返回值就用 实际的步数 这样可以方便后面的递归用一个cache 二维列表来记录结果避免重复的运算 import os
import sysn, m map(int, input().split())
lst [list(map(int, input().split())) for _ in range(n)]
# 递归搜索 保存计算结果后面不再运算重复路线 记忆化搜索
cache [[-1] * m for _ in range(n)]
# 记忆化搜索: -1代表没记录当前位置所能达到的最远距离其他值代表已经记录了当前位置所能达到的最远距离并且就是记录的就是当前位置最远距离def dfs(x, y): # 当前位置所能达到的最远距离if cache[x][y] ! -1: # 如果被记录过了return cache[x][y] # 就不再往下计算了并且返回当前位置所能达到的最远距离ans 1for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:xx dx xyy dy yif 0 xx n and 0 yy m and lst[xx][yy] lst[x][y]:ans max(dfs(xx, yy) 1, ans)cache[x][y] ans # 每次走到尽头了就记录一下当前这条路线走了几步距离return ans # 返回当前位置所能达到的最远距离res 0
for i in range(n):for j in range(m):res max(dfs(i, j), res)print(res)
