首页 > 试题广场 >

小A与小B

[编程题]小A与小B
小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。

输入描述:



输出描述:
如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。
示例1

输入

4 5
. . . . .
. # # # .
. . . # D
. . C # .

输出

YES
3

备注:
算法知识视频讲解
开通博客
头像 hx073269
发表于 2020-06-04 11:26:05
代码思想：每秒对小B进行两次BFS，对小A进行一次BFS，当他们碰见对方走过的路就跳出循环输出此时时间即可，具体可见代码。时间复杂度：O(nm)代码部分： #include<bits/stdc++.h> using namespace std; //定义队列节点 struct node 展开全文
去ta的博客 赞 (23) 回复(1) 收起
头像 ray52033
发表于 2020-06-07 09:54:39
BFS 这道题要求小A和小B最早的相遇时间。而小A的行走规则是：每次可以走8个方向，每次走一步小B的行走规则是：每次可以走4个方向，但每次走两步（两步不一定是要同方向） 于是我们可以在每秒分别在对小A，小B每秒的行走进行讨论：分别建立小A，小B的队列，依次对他俩进行，并分别记录下行走中可以到达的点， 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 zzugzx
发表于 2020-06-04 11:54:08
题目链接 题意：题解： AC代码 /* Author:zzugzx Lang:C++ Blog:blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #define fi 展开全文
去ta的博客 赞 (9) 回复(1) 收起
头像 昵称很长很长真是太好了
发表于 2020-06-04 13:44:28
题解：这个题属于走迷宫类型问题的一个升级版吧，不同之处在于一秒钟小A走一步，小B可以走两步，这两种事件是同时发生的，所以我们每秒钟让A扩散一步，让B扩散两步。两个人走过的路径分别用visited[0][maxn][maxn]visited[1][maxn][maxn]来进行表示。小a走的时候1.检查 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 ______________________
发表于 2020-08-20 16:23:51
双向搜索，bfs，用pair来存储坐标方便很多由于d要走两次，不太方便，所以我们直接bfs两次就好了 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Kur1su
发表于 2020-06-04 15:27:33
Description 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 钻石柠檬
发表于 2024-06-02 11:45:46
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int n,ans=0; int a[maxn]; int col[maxn],row[maxn],line[maxn],rline[maxn]; vo 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hairtail
发表于 2020-07-11 14:59:01
题目描述 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 19_hanhan
发表于 2020-06-08 19:36:53
题目 题目描述： 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。 小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向。 请问 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 一衍一
发表于 2020-06-04 11:48:56
题意:走迷宫,问能不能碰头,能的话,什么时候碰头题解:广搜,定义一个时间戳,分别把两个开始点能走到的点的时间戳+1,然后把这些能走到的点,的能走到的点的时间戳+2......(已经走过的点不能再往回走)如果最后队列为空,仍没有可以重合的点,输出NO否则输出YES,合最开始重合的时间戳 #includ 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

枚举
难度：
0条回答 11浏览

热门推荐

相关试题

小A与小B

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号