网站群建设的目的意义,做网站可以自由职业吗,wordpress转域名收费,网站建设对网络营销有哪些影响双向bfs适用于知道起点和终点的状态下使用#xff0c;从起点和终点两个方向开始进行搜索#xff0c;可以非常大的提高单个bfs的搜索效率同样#xff0c;实现也是通过队列的方式#xff0c;可以设置两个队列#xff0c;一个队列保存从起点开始搜索的状态#xff0c;另一个…双向bfs适用于知道起点和终点的状态下使用从起点和终点两个方向开始进行搜索可以非常大的提高单个bfs的搜索效率同样实现也是通过队列的方式可以设置两个队列一个队列保存从起点开始搜索的状态另一个队列用来保存从终点开始搜索的状态如果某一个状态下出现相交的情况那么就出现了答案
用一张图来进行说明 当两种颜色相遇的时候说明两个方向的搜索树遇到一起这个时候就搜到了答案。
例题1:走迷宫
问题描述 一个迷宫由 R R R行 C C C列格子组成有的格子里有障碍物不能走有的格子是空地可以走。 给定一个迷宫求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走不能斜着走。
输入
第一行是两个整数 和 代表迷宫的长和宽。 1 ≤ R C ≤ 40 ) 1≤ RC ≤ 40) 1≤RC≤40) 接下来是 行每行 个字符代表整个迷宫。 空地格子用‘.’表示有障碍物的格子用‘#’表示。 迷宫左上角和右下角都是‘.’。
输出
输出从左上角走到右下角至少要经过多少步即至少要经过多少个空地格子。计算步数要包括起点和终点。
样例输入
5 5
..###
#....
#.#.#
#.#.#
#.#..样例输出
9代码如下
#include iostream
#include queue
using namespace std;
int r, c;
const int N 45;
char mp[N][N];
typedef pairint, intPII;
#define x first
#define y second
int vis[N][N];
int flag;
int dis[N][N];
int dx[] {0, 0, 1, -1}, dy[] {1, -1, 0, 0};int dbfs() {queuePIIq1, q2;//q1为从前往后搜q2为从后往前搜dis[1][1] 1;dis[r][c] 1;vis[1][1] 1;//q1标记为1vis[r][c] 2;//q2标记为2//如果某状态下当前节点和准备扩展节点的状态相加为3//说明相遇q1.push({1, 1});q2.push({r, c});PII t;while (q1.size() q2.size()) {if (q1.size() q2.size()) {每次扩展搜索树小的队列 flag1表示从前往后搜的队列flag0表示从后往前搜的队列t q1.front();q1.pop();flag 1;//q1标记为1} else {t q2.front();q2.pop();flag 0;//q2标记为0}for (int i 0; i 4; i) {int xx t.x dx[i];int yy t.y dy[i];if (xx 1 xx r yy 1 yy c mp[xx][yy] .)if (!dis[xx][yy])if (flag) {vis[xx][yy] 1;dis[xx][yy] dis[t.x][t.y] 1;q1.push({xx, yy});} else {vis[xx][yy] 2;dis[xx][yy] dis[t.x][t.y] 1;q2.push({xx, yy});} else {if (vis[xx][yy] vis[t.x][t.y] 3)//相遇 {return dis[xx][yy] dis[t.x][t.y];}}}}return -1;
}int main() {cin r c;for (int i 1; i r; i)for (int j 1; j c; j)cin mp[i][j];cout dbfs() endl;return 0;
}参考文章链接https://blog.csdn.net/weixin_43501684/article/details/90147421
