首页 > 小A与小B
头像 hx073269
发表于 2020-06-04 11:26:05
代码思想:每秒对小B进行两次BFS,对小A进行一次BFS,当他们碰见对方走过的路就跳出循环输出此时时间即可,具体可见代码。时间复杂度:O(nm)代码部分: #include<bits/stdc++.h> using namespace std; //定义队列节点 struct node 展开全文
头像 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 展开全文
头像 ray52033
发表于 2020-06-07 09:54:39
BFS 这道题要求小A和小B最早的相遇时间。而小A的行走规则是:每次可以走8个方向,每次走一步小B的行走规则是:每次可以走4个方向,但每次走两步(两步不一定是要同方向) 于是我们可以在每秒分别在对小A,小B每秒的行走进行讨论:分别建立小A,小B的队列,依次对他俩进行,并分别记录下行走中可以到达的点, 展开全文
头像 昵称很长很长真是太好了
发表于 2020-06-04 13:44:28
题解:这个题属于走迷宫类型问题的一个升级版吧,不同之处在于一秒钟小A走一步,小B可以走两步,这两种事件是同时发生的,所以我们每秒钟让A扩散一步,让B扩散两步。两个人走过的路径分别用visited[0][maxn][maxn]visited[1][maxn][maxn]来进行表示。小a走的时候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> 展开全文
头像 Kur1su
发表于 2020-06-04 15:27:33
Description 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置,而他们希望能够迅速找到对方,然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置,而小B每次可以移动两次位置,小A移动的方向是上下左右左上左下右上右下8个方向,小B移动的方向是上下左右4个方向,请问他们最早什么时候能够 展开全文
头像 hairtail
发表于 2020-07-11 14:59:01
题目描述 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置,而他们希望能够迅速找到对方,然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置,而小B每次可以移动两次位置,小A移动的方向是上下左右左上左下右上右下8个方向,小B移动的方向是上下左右4个方向,请问他们最早什么时候能够找到对方 展开全文
头像 19-hanhan
发表于 2020-06-08 19:36:53
题目 题目描述: 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置,而他们希望能够迅速找到对方,然后再考虑如何逃离迷宫的事情。 小A每次可以移动一个位置,而小B每次可以移动两次位置,小A移动的方向是上下左右左上左下右上右下8个方向,小B移动的方向是上下左右4个方向。 请问 展开全文
头像 一衍一
发表于 2020-06-04 11:48:56
题意:走迷宫,问能不能碰头,能的话,什么时候碰头题解:广搜,定义一个时间戳,分别把两个开始点能走到的点的时间戳+1,然后把这些能走到的点,的能走到的点的时间戳+2......(已经走过的点不能再往回走)如果最后队列为空,仍没有可以重合的点,输出NO否则输出YES,合最开始重合的时间戳 #includ 展开全文
头像 精神病科黄主任
发表于 2020-06-07 21:48:07
分别对两个人进行bfs 计算出到达每个点的最短时间然后枚举两个人都能达到的点,最晚到的那个人的时间就是在这个点的相遇时间。因为要求时间最小,所以总体维护一个最小值即可对于判断点两个人是不是能同时达到,应该判断这个点两个人是不是能在有限时间内到,而不是这个点是不是障碍比如1 3C#D答案显然是NO 不 展开全文