链接：https://ac.nowcoder.com/acm/problem/23486 来源：牛客网
小A与小B 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 小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 输入 复制 4 5 . . . . . . # # # . . . . # D . . C # . 输出 复制 YES 3 备注: 1 ≤ n , m ≤ 1000 1 \leq n,m \leq 1000 1≤n,m≤1000
解题：双向bfs，（HDU3085） 这种情况很明显是用BFS方法搜索，复杂度是O(nm) 由于是两个人，所以进行双向BFS 将两个人的初始位置放入两个队列，记为第0秒 然后按各自的方向进行BFS搜索 由于小B可以走两次，直接BFS两次 然后分别用两个vis数组标记两个人走过的点 如果发现有一个走过的点另一个人也走过，说明相遇了 此时的时间就是最短相遇时间 如果发现两个人的队列都空了，还没发现他俩相遇，那就是不可能相遇了
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<stack> #include<queue> #include<set> #include<map> #include<time.h> #include<vector> using namespace std; #define ll long long int n,m; char Map[1010][1010]; int vis[2][1005][1005]; //0代表小A，1代表小B int dir[8][2] = {-1,0,1,0,0,-1,0,1,-1,-1,1,-1,-1,1,1,1}; queue<pair<int,int>> q[2]; //queue队列 int bfs(int x) { int sz = q[x].size(); while(sz--){ pair<int,int> p = q[x].front(); q[x].pop(); //A和B的方向不同，A有8个方向，B可以走4个方向 for(int k=0; k<(x==1?4:8); ++k){ int dx = p.first+dir[k][0]; int dy = p.second+dir[k][1]; if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&Map[dx][dy]!='#'&&!vis[x][dx][dy]){ if(x==0&&vis[1][dx][dy]) return 1; //相遇 else if(x==1&&vis[0][dx][dy]) return 1; //相遇 vis[x][dx][dy] = 1; q[x].push(make_pair(dx,dy)); } } } return 0; //这步没有相遇 } int solve() { int res = 0; while(!q[0].empty()||!q[1].empty()){ //只要不为空，就继续拓展 res++; //时间+1，1个时间内，A走一步，B走两步 if(bfs(0)) return res; if(bfs(1)) return res; if(bfs(1)) return res; } return -1; } int main() { cin>>n>>m; for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ cin>>Map[i][j]; //起始位置入队列 if(Map[i][j]=='C') q[0].push(make_pair(i,j)); if(Map[i][j]=='D') q[1].push(make_pair(i,j)); } } int ans = solve(); if(ans==-1) cout<<"NO"; else{ cout<<"YES"<<endl; cout<<ans<<endl; } return 0; }