错误版本
本题可以理解为矩阵上的单源最短路径，因为数据不是很大，我们可以使用BFS进行搜索PLMM和猫到达图中所有点的最短路径。但是题目加上了附属条件，PLMM走的步数是有限的，而且猫的嗅觉也是有限的。所以我们可以求完最短路径之后，找到一个可以同时满足两个要求的点，如果可以找到，则更新答案。不能则输
展开全文
思路
显然是图论问题，而看到最短距离就应该优先使用BFS。
先后用BFS计算人和猫到其各自范围中任意合法位置的最短距离。注意处于人移动范围的合法位置会由于障碍物'*'的阻碍无法到达，而猫的嗅觉范围可以无视障碍物到达，这一点在BFS的代码中是否将新位置加入队列中的判断条件上有所体现。
最后遍历两者都
展开全文
题意：给定二维字符矩阵，‘*’ 代表障碍且不能通过，‘.’代表空且可以通过，一人位于点(x1,y1)，一猫位于点(x2,y2)，当人走到与猫的曼哈顿距离小于r2时人停止走动，此时猫会向人走来。人的活动范围为r1，代表人不能走到与(x1,y1)曼哈顿距离大于r1的点上，注意：当且仅当人走到与(x2，y
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
