首页 > 小喵觅食
开通博客写题解
头像 dilingtian
发表于 2022-11-18 21:15:13
错误版本 本题可以理解为矩阵上的单源最短路径，因为数据不是很大，我们可以使用BFS进行搜索PLMM和猫到达图中所有点的最短路径。但是题目加上了附属条件，PLMM走的步数是有限的，而且猫的嗅觉也是有限的。所以我们可以求完最短路径之后，找到一个可以同时满足两个要求的点，如果可以找到，则更新答案。不能则输 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 Guoxu_
发表于 2024-02-21 17:21:35
思路 显然是图论问题，而看到最短距离就应该优先使用BFS。 先后用BFS计算人和猫到其各自范围中任意合法位置的最短距离。注意处于人移动范围的合法位置会由于障碍物'*'的阻碍无法到达，而猫的嗅觉范围可以无视障碍物到达，这一点在BFS的代码中是否将新位置加入队列中的判断条件上有所体现。 最后遍历两者都 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客399999999999号
发表于 2022-11-19 10:01:40
题意：给定二维字符矩阵，‘*’ 代表障碍且不能通过，‘.’代表空且可以通过，一人位于点(x1,y1)，一猫位于点(x2,y2)，当人走到与猫的曼哈顿距离小于r2时人停止走动，此时猫会向人走来。人的活动范围为r1，代表人不能走到与(x1,y1)曼哈顿距离大于r1的点上，注意：当且仅当人走到与(x2，y 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”