字节笔试dp试题

A要去救B,A在(0,0),B在(M,N),K个坏人在M,N,0,0构成的矩形的某个坐标里。当A与坏人的距离小于等于1(上下左右格子遇到的时候),A会被发现。求问A救到B的路径数量,M,N,K<=1000.A只能向右向上移动(横纵坐标+1这样移动)。
AC没成功😂
请问各位牛友有会解答的吗?
全部评论
这样行不行?用并查集将所有坏人和临近节点放到一个集合里,然后dfs剩余的点。
1 回复 分享
发布于 2022-07-08 20:01
在矩阵中把A不能走的位置置为1,可以走的位置为0,这样转化为迷宫问题,用深度优先算法就可以了
点赞 回复 分享
发布于 2022-07-08 20:53
先预处理成常规的2维地图,然后常规dp就行了。 dp[i][j]=mat[i][j]?0:dp[i-1][j]+dp[i][j-1]
点赞 回复 分享
发布于 2022-07-09 18:32
这还可以呀,先遍历一遍矩阵将矩阵中的坏人一圈记录为石头,然后不就是leetcode的原题了吗
点赞 回复 分享
发布于 2022-07-11 00:19
这个在leetcod的原型就是有障碍的机器人选路
点赞 回复 分享
发布于 2022-07-11 20:07

相关推荐

小火柴燃烧吧:接啊,接了之后反手在咸鱼找个大学生搞一下,量大从优
点赞 评论 收藏
分享
评论
1
8
分享
牛客网
牛客企业服务