字节笔试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没成功😂
请问各位牛友有会解答的吗？
AC没成功😂
请问各位牛友有会解答的吗？
2022-07-08 19:36 中国科学技术大学 数据库工程师
关注
全部评论
这样行不行？用并查集将所有坏人和临近节点放到一个集合里，然后dfs剩余的点。
牛客623162032号
门头沟学院 Java
这个在leetcod的原型就是有障碍的机器人选路
长不大的程序猿
哈尔滨理工大学 C++
这还可以呀，先遍历一遍矩阵将矩阵中的坏人一圈记录为石头，然后不就是leetcode的原题了吗
The_last_piece
哈尔滨工业大学 C++
先预处理成常规的2维地图，然后常规dp就行了。 dp[i][j]=mat[i][j]?0:dp[i-1][j]+dp[i][j-1]
牛客453951331号
Python
在矩阵中把A不能走的位置置为1，可以走的位置为0，这样转化为迷宫问题，用深度优先算法就可以了
相关推荐
查看11道真题和解析
OPPO公司福利 1133人发布