【算法学习之路】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;
    //初始化为-1
    for (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;
}