【算法学习之路】13.BFS

前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

一.BFS

1.BFS广度优先搜索，是一种用于遍历或搜索树或图的算法。所谓广度优先就是说按照圈层搜索
2.在搜索算法中该BFS常常指利用队列实现广度优先搜索，从而寻找最短距离。与图论中的BFS算法有一定的相似之处，但不完全相同。通常用来解决寻找最短路径的问题
3.在搜索算法中，BFS常常被用来在网格中搜索，寻找最短路径

二.题目

1

洛谷P1443 马的遍历

寻找网格中一点到其他点的最短距离，显然用BFS。
思路：
（1）因为马只能走“日”字点，所以不是所有的都会走到，可以先把答案数组全部赋值成 - 1，后面再搜索改变能够走到的点的值。

（2）“日”字的八个方向，可以通过对行列坐标 x y做加减得到：

（3）队列用STL实现，进行BFS，过程中要维护距离数组。

#include <iostream>
#include <queue>
using namespace std;
int dx[8] = { -1,-2,-2,-1,1,2,2,1 };//移动的x轴
int dy[8] = { -2,-1,1,2,2,1,-1,-2 };//移动的y轴
struct node {//坐标点int x, y;
};
queue<struct node> q;//队列
int n, m, sx, sy;
int ans[405][405];//答案数组
int f[405][405];//判断是否经过
int main() {cin >> n >> m >> sx >> sy;//初始化为-1for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {ans[i][j] = -1;}}struct node a, ne;ne.x = sx, ne.y = sy;//将开始点写入ans[sx][sy] = 0;f[sx][sy] = 1;//标记q.push(ne);//放入数组while (!q.empty()) {//为空才停a = q.front();q.pop();for (int i = 0; i < 8; i++) {//往8个方向走ne.x = a.x + dx[i];ne.y = a.y + dy[i];if (ne.x >= 1 && ne.x <= n && ne.y >= 1 && ne.y <= m && f[ne.x][ne.y] == 0) {//如果在棋盘且未走过q.push(ne);f[ne.x][ne.y] = 1;ans[ne.x][ne.y] = ans[a.x][a.y] + 1;//加一}}}//输出for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {printf("%-5d", ans[i][j]);}printf("\n");}return 0;
}

2

洛谷P8693 [蓝桥杯 2019 国 AC] 大胖子走迷

思路：
求小明从起点走到迷宫终点的最少时间，用广度优先搜索算法 BFS。

相比一般的 BFS 走迷宫问题，本题需要处理好以下几个关键点：

1）在某一个点小明除了可以向当前位置的上、下、左、右移动单位 1 的距离，还可以停留在原地不动。这个停在原地不动每次会耗费 1 个单位的时间，这个耗时是有意义的，因为耗时达到 k 或 2×k 时，小明会瘦身，这样瘦身前不能走的格子，瘦身后可以走了。因此，在当前位置停留等待的状态也要入队。当然，如果小明已经瘦身到了 1×1，就没有必要休息等待了，此时再等待纯属无意义地耗费时间。

2）由于小明身体形态有 这三种情况。为此，设置一个变量 flag 来表示这三种不同的形态。初始时，flag 的值为 2，表示小明此时为 5×5形态；当耗时达到 k 时，flag 的值为 1，表示小明此时瘦身为 3×3 形态；当耗时达到 2×k 时，flag 的值为 0，表示小明此时再瘦身为 1×1 形态。这样进行 flag 值的设置，在后面进行检测时也就带来统一的好处。

3）不同于一般的迷宫，最多表示 N×N 个格子的结点入队。因为一个结点处等待也需入队，这样入队的结点个数会远远超过 N×N 个。循环数组模拟队列。

#include <stdio.h>
#include <string.h>
#define MAXLEN 90000
struct Node {int x, y, time;
};
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int vis[305][305] = { 0 };
char map[305][305];
int n, k;
struct Node q[MAXLEN + 5];
void bfs() {struct Node cur;cur.x = 3, cur.y = 3;cur.time = 0;int front = 0, rear = 0;q[rear++] = cur;int flag = 2;while (front != rear) {cur = q[front];front = (front + 1) % MAXLEN;if (cur.time == k) {flag = 1;}if (cur.time == 2 * k) {flag = 0;}if (flag != 0) {q[rear].x = cur.x; q[rear].y = cur.y;q[rear].time = cur.time + 1;rear = (rear + 1) % MAXLEN;}int m, i, j;for (m = 0; m < 4; m++) {int nx = cur.x + dx[m];int ny = cur.y + dy[m];if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0) {int ok = 1;for (i = nx - flag; ok && (i <= nx + flag); i++) {for (j = ny - flag; j <= ny + flag; j++) {if (i < 1 || i > n || j > n || j < 1 || map[i][j] == '*') {ok = 0;break;}}}if (ok) {if (nx == n - 2 && ny == n - 2) {printf("%d\n", cur.time + 1);return;}vis[nx][ny] = 1;q[rear].x = nx;q[rear].y = ny;q[rear].time = cur.time + 1;rear = (rear + 1) % MAXLEN;}}}}
}int main() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++) {scanf("%s", &map[i][1]);}bfs();return 0;
}