首页 > 笔经面经 > 7.31科大讯飞笔试研发算法题第三题障碍

7.31科大讯飞笔试研发算法题第三题障碍

头像
阿木木_w #科大讯飞2021秋招提前批#
发布于 2021-07-31 22:32:14 APP内打开
赞 1 | 收藏 5 | 回复9 | 浏览3922
第三题也是3.85,后来想了一下这个特例
.  . # . . .
# . . . # .
# ### # .
返回值应该是0
有一个想法,用二维动态规划做,表示到达当前点的最小障碍数;
首先需要从[0,0]做dfs,找出一个无障碍可直接到的通道,即步数为0;
然后循环判断dp=min(上,下,左,右)(+1)根据该处是否有障碍判断是否需要+1;
最后输出dp[M][N]的答案;

9条回帖

回帖
加载中...
话题 回帖

相关热帖

笔经面经近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐