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