【每日一题】小A与小B
小A与小B
https://ac.nowcoder.com/acm/problem/23486
题目
题目描述： 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。
小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向。
请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。
输入描述：
第一行两个整数N，M分别表示迷宫的行和列。\\接下来一个N\times M 的矩阵\\其中"C"表示小A的位置,"D"表示小B的的位置，\\
"＃"表示不可通过的障碍，"."则是可以正常通过的位置。\\字符用空格隔开\\第一行两个整数N，M分别表示迷宫的行和列。
接下来一个N×M的矩阵
其中"C"表示小A的位置,"D"表示小B的的位置，
"＃"表示不可通过的障碍，"."则是可以正常通过的位置。
字符用空格隔开
输出描述：
如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。
解析
1）知识点
这道题是一道有点复杂的bfs，这里是双向广搜。
2）看题目
题目简单来说就是，按地图走路，两个人的走路方法也不一样，问两个人能不能相遇，相遇的最短回合数是多少。
3）算法分析
- 这道题难就难在，两个人的走路方法是不一样的。如果两个人的走路方法是一样的，我们可以求出两个人之间的距离，然后除3就好了。
- 但是现在是不一样的。我们这里就可以分两个人bfs（用点技巧可以合并成一个bfs，这一点先不管）。
- 现在我们知道的是，a可以走8个方向，每回合一步。b可以走四个方向，每回合两步。
- 也就是说我们不考虑走路方法的话，每回合就是让a走一步，让b走两步：
if (bfs(0)) return step; //a走一次 if (bfs(1)) return step; if (bfs(1)) return step; //b走两次 //这里bfs用来判断，a和b是否在这一回合会碰到对方。 - 然后问题就是bfs怎么实现了。
- 其实和我们原来普通的bfs是差不多的，判定条件就是是否到达过了对面到达过的地方。
4）算法操作
- 首先就是走路的函数，用来计算到底走了多少次：
int calc() { int step = 1; while (!que[0].empty() || !que[1].empty()) { if (bfs(0)) return step; //a走一次 if (bfs(1)) return step; if (bfs(1)) return step; //b走两次 //判别成功表示相遇了 step++; } return -1; } - 然后呢，我们就可以开始写bfs函数了。在那之前，我们先写一下bfs越界和走过的位置的判断函数：
bool judge(Node x, int res) { if (!mp[x.x][x.y]) return false;//用的是有边框的地图，所以可以减少特判 if (vis[x.x][x.y][res]) return false; return true; } - 最后我们正常的来一遍bfs就可以啦：
bool bfs(int x) { int T = que[x].size();//消耗掉原来的步数 while (T--) { Node top = que[x].front(); que[x].pop(); for (int i = 0; i < 8 - 4 * x; i++) { Node nxt; nxt.x = top.x + walk[i][0]; nxt.y = top.y + walk[i][1]; if (vis[nxt.x][nxt.y][x ^ 1]) return true; if (judge(nxt, x)) { que[x].push(nxt); vis[nxt.x][nxt.y][x] = 1; } } } return false; }
5）打代码
- 首先，输入我们的地图，留下外面的边框，用于减少特判。
- 然后就开始算步数了，看上面就好啦。
- 下面全代码~
AC代码
#include <iostream>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 1e3 + 7;
struct Node {
int x, y;
};
int n, m;//行列数量
int mp[MAX][MAX], vis[MAX][MAX][2];//mp为1的位置表示可走，vis为1表示走过（两个人的）
int walk[8][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 },
{ 1, 1 }, { -1, 1 }, { 1, -1 }, { -1, -1 } };//方向
queue<Node> que[2];//两个人的队列
//全局变量区
int calc();
bool judge(Node x, int res);
bool bfs(int x);
//函数预定义区
int main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
char ch; cin >> ch;
if (ch != '#') {
mp[i][j] = 1;
if (ch == 'C') {
que[0].push(Node{ i, j });
vis[i][j][0] = 1;
}
else if (ch == 'D') {
que[1].push(Node{ i, j });
vis[i][j][1] = 1;
}
}
}
int ans = calc();
if (ans == -1) cout << "NO" << endl;
else {
cout << "YES" << endl;
cout << ans << endl;
}
return 0;
}
int calc() {
int step = 1;
while (!que[0].empty() || !que[1].empty()) {
if (bfs(0)) return step;
//a走一次
if (bfs(1)) return step;
if (bfs(1)) return step;
//b走两次
//判别成功表示相遇了
step++;
}
return -1;
}
bool judge(Node x, int res) {
if (!mp[x.x][x.y]) return false;
if (vis[x.x][x.y][res]) return false;
return true;
}
bool bfs(int x) {
int T = que[x].size();//消耗掉原来的步数
while (T--) {
Node top = que[x].front(); que[x].pop();
for (int i = 0; i < 8 - 4 * x; i++) {
Node nxt;
nxt.x = top.x + walk[i][0];
nxt.y = top.y + walk[i][1];
if (vis[nxt.x][nxt.y][x ^ 1]) return true;
if (judge(nxt, x)) {
que[x].push(nxt);
vis[nxt.x][nxt.y][x] = 1;
}
}
}
return false;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
得物app公司福利 402人发布
