美团第四题这样对吗

美团第四题,我的想法是转换成走迷宫,每当有通路时把地雷的范围+1,也就是原来的雷的相邻点也变成雷,然后继续走迷宫,直到没有通路时,加雷的次数等于最大的最小距离#美团信息集散地##美团4.8笔试##美团笔试##美团实习#
全部评论
第一步 预处理出网格中每个点到地雷的最短距离dis 用个队列bfs就行 一开始把所有地雷放进去 慢慢往外扫 第二步 两种方法 1、二分答案mid 判断起点和终点仅使用dis<=mid的点是否联通 2、优先队列 把起点的坐标和dis放进去 然后沿着四个方向往外扫 走到终点则停止 优先队列的性质可以保证优先经过距离地雷远的点
4 回复 分享
发布于 2023-04-08 23:02 北京
我也是这样想的,但不知道会不会超时,考场上已经没时间了。。。雷区膨胀后有什么办法可以利用膨胀前的结果来高效计算通路是否存在吗?
点赞 回复 分享
发布于 2023-04-08 22:14 北京
Dp吧我觉得
点赞 回复 分享
发布于 2023-04-08 22:16 辽宁
二分最大的最小距离,然后用搜索来Check
点赞 回复 分享
发布于 2023-04-08 22:17 广西
搞个dp先弄一个每个格子的最小值。然后遍历这个dp找最小路径,不知道对不对
点赞 回复 分享
发布于 2023-04-08 22:19 辽宁
https://www.nowcoder.com/discuss/474321361452666880?sourceSSR=users
点赞 回复 分享
发布于 2023-04-08 22:38 北京

相关推荐

拉丁是我干掉的:把上海理工大学改成北京理工大学。成功率增加200%
点赞 评论 收藏
分享
安静的垂耳兔在泡澡:ks已经第八次投递了,它起码挂了还让你再投,不错了
点赞 评论 收藏
分享
点赞 2 评论
分享
牛客网
牛客企业服务