网站建设的工作职责是什么,品牌建设 企业发言,怎么创建自己的域名,免费手机网站开发BFS广度优先搜索
1. 概念理解
广度优先搜索(BFS)是指#xff0c;以一个起点(原点、结点、根)为基本点#xff0c;向其所要搜索的方向扩散#xff0c;并最终到达目标点的搜索方法。
2. 应用方向
有迷宫问题、层序遍历等应用。
3. 迷宫问题
以迷宫问题为例。
当想要从左…BFS广度优先搜索
1. 概念理解
广度优先搜索(BFS)是指以一个起点(原点、结点、根)为基本点向其所要搜索的方向扩散并最终到达目标点的搜索方法。
2. 应用方向
有迷宫问题、层序遍历等应用。
3. 迷宫问题
以迷宫问题为例。
当想要从左上角访问到右下角的时候需要以左上角的起点作为基准点然后以下左上右的方式进行扩散当到达右下角的时候停止扩散输出路径最少的步数.
3.1 步骤 将起点入队并将其作为基准点进行搜索 依次遍历基准点的周围点看是否能通行 2.1. 如果能够通行那么就将这个点入队 2.2. 如果不能通行跳过判断下一个点 能通行入队如果需要就保存路径至相应的坐标数组
3.2 代码
#include iostream
#include queueusing namespace std;// 定义二维坐标
typedef pairint, int PII;void bfs(int *arr[], const int row, const int col) {queuePII q;// 1. 将起点入队q.push({ 0,0 });arr[0][0] 2;// 设置为访问过// 方向数组int dx[] { 1,0,-1,0,1 };int dy[] { 0,-1,0,1,1 };// 下左上右右下// 坐标数组PII pre[100][100];// 2. 看起点周围是否有可行的点while (!q.empty()) {PII top q.front();q.pop();for (int i 0; i 5; i) {int xx dx[i] top.first;int yy dy[i] top.second;// 越界if (xx 0 || yy 0 || xx row || yy col) continue;// 不是路if (arr[xx][yy] ! 0) continue;q.push({ xx,yy });arr[xx][yy] 2;pre[xx][yy] top;// 存上一个位置}}if (q.empty()) {// 打印路径 cout ( row , col ) endl;int i row - 1;int j col - 1;while (i || j) {PII tmp pre[i][j];cout ( tmp.first1 , tmp.second1 ) endl;i tmp.first;j tmp.second;}}else {cout 没有通路 endl;}
}int main() {// 构建迷宫int m, n;cin m n;int** arr new int* [m];for (int i 0; i m; i) {arr[i] new int[n];}for (int i 0; i m; i) {for (int j 0; j n; j) {cin arr[i][j];}}// 从00开始到m-1n-1结束bfs(arr, m, n);// 释放内存for (int i 0; i m; i) {delete[] arr[i];}delete[] arr;return 0;
}
