关于bfs:BFS算法模板与练习

文章和代码曾经归档至【Github 仓库：algorithms-notes】或者公众号【AIShareLab】回复 算法笔记 也可获取。

首先，计算机中罕用的数据结构是栈和队列。

栈：先进后出，通常利用是递归，DFS。
队列：先进先出，通常利用是 BFS。

过程如下所示：

每次取出队头元素，并且把其拓展的元素放在队尾。

下面过程可知，遍历的过程以及入队的过程都是依照 BFS(1 2 3…10) 的程序进行的

BFS 宽搜：每次扩大最早的点。（因而能够找到一条最短的门路）

DFS 深搜：每次扩大第一个点。

BFS 中常见问题，迷宫问题。

1. 判重

入队时判重，保障每个边只会入队一次，从而保障工夫复杂度是线性的。（因而有判重数组的存在，宽搜也能够搜寻环），st[]。

2. 队列

queue <--- 初始状态 // 队列保留初始状态
while(queue 非空)
{
    t < --- 队头 // t 保留队头
    for(拓展 t)
    {
        ver < --- 新节点 // 拓展 t 失去的新节点
        if(!st[ver]) // 如果拓展的新节点没有被搜寻过
        {ver ----> 队尾 // 保留至队尾}
    }
}

阿尔吉侬是一只聪慧又慵懒的小白鼠，它最善于的就是走各种各样的迷宫。

明天它要挑战一个十分大的迷宫，研究员们为了激励阿尔吉侬尽快达到起点，就在起点放了一块阿尔吉侬最喜爱的奶酪。

当初研究员们想晓得，如果阿尔吉侬足够聪慧，它起码须要多少工夫就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来示意。

字符 S 示意阿尔吉侬所在的地位，字符 E 示意奶酪所在的地位，字符 # 示意墙壁，字符 . 示意能够通行。

阿尔吉侬在 1 个单位工夫内能够从以后的地位走到它上下左右四个方向上的任意一个地位，但不能走出地图边界。

输出格局

第一行是一个正整数 T，示意一共有 T 组数据。

每一组数据的第一行蕴含了两个用空格离开的正整数 R 和 C，示意地图是一个 R×C 的矩阵。

接下来的 R 行形容了地图的具体内容，每一行蕴含了 C 个字符。字符含意如题目形容中所述。保障有且仅有一个 S 和 E。

输入格局

对于每一组数据，输入阿尔吉侬吃到奶酪的起码单位工夫。

若阿尔吉侬无奈吃到奶酪，则输入“oop!”（只输入引号外面的内容，不输入引号）。

每组数据的输入后果占一行。

数据范畴

$1<T≤10$,
$2≤R,C≤200$

输出样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输入样例：

5
1
oop!

code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;
// pair 有两个属性，first 和 second，倡议宏定义为 x 和 y，不便了解
typedef pair<int, int> PII;

const int N = 210;

int n, m;
// 存储地图
char g[N][N];
// 存储坐标
int dist[N][N];

int bfs(PII start, PII end)
{
    queue<PII> q;
    memset(dist, -1, sizeof dist);

    dist[start.x][start.y] = 0;
    q.push(start);

    // 存储坐标位移
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {auto t = q.front();
        q.pop();
        // 遍历坐标
        for (int i = 0; i < 4; i ++)
        {int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;  // 出界
            if (g[x][y] == '#') continue;  // 障碍物
            if (dist[x][y] != -1) continue;  // 之前曾经遍历过

            dist[x][y] = dist[t.x][t.y] + 1;

            if (end == make_pair(x, y)) return dist[x][y];

            q.push({x, y});
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T --)
    {scanf("%d%d", &n, &m);
        // 一共读取 n 行，每行是一个一维字符串
        for (int i = 0; i < n; i ++) scanf("%s", g[i]);
        // 不必定义成全局变量，如果定义全局变量会造成关键字抵触。// 如果想定义为全局变量，能够思考换个名称例如 end1 等。PII start, end;
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
                if (g[i][j] == 'S') start = {i, j};
                else if (g[i][j] == 'E') end = {i, j};

        int distance = bfs(start, end);
        if (distance == -1) puts("oop!");
        else printf("%d\n", distance);
    }

    return 0;
}

有 N 个瓶子，编号 1∼N，放在架子上。

比方有 5 个瓶子：

2 1 3 5 4

要求每次拿起 2 个瓶子，替换它们的地位。

通过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简略的状况，显然，至多须要替换 2 次就能够复位。

如果瓶子更多呢？你能够通过编程来解决。

输出格局

第一行蕴含一个整数 N，示意瓶子数量。

第二行蕴含 N 个整数，示意瓶子目前的排列情况。

输入格局

输入一个正整数，示意至多替换多少次，能力实现排序。

数据范畴

$1≤N≤10000,$

输出样例 1：

5
3 1 2 5 4

输入样例 1：

输出样例 2：

5
5 4 3 2 1

输入样例 2：

这道题能够采纳暴力思路，通过观察能够发现，咱们每一个数都必须回到它本人的地位上，比方 1 必须在第一位，2 必须在第二位上。因为每个数必须回到本人的地位，间接从 1 枚举到 n，如果以后地位的数不等于它的下标，那么咱们就必须要把它给替换掉。设以后地位为 i
的话，那么咱们就从 i+ 1 开始往后枚举，直到找到对应的 a[j] 和咱们的 i 相等，那么咱们就把上个数替换，把替换次数 ++。因为每个瓶子都要归位，因而不会呈现多余的步骤，可知是起码的次数。

code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;
int a[N], sum;

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++)
        if(a[i] != i)
            for(int j = i + 1; j <= n; j ++)
                if(a[j] == i) 
                {swap(a[j], a[i]);
                    sum ++ ;
                    break;
                }
    cout << sum << endl;
    return 0;
}

初始状态如下所示：

其中，每个地位向所在的瓶子连一条有向线。

出度是 1，入度是 1，这样的一个环称为置换。

最终心愿的状态是变成五个自环。

替换两个瓶子对于环产生的影响

替换同一个环内的点：裂成两个环。
替换不同环内的点：合并两个环。

可见，替换瓶子实际上扭转了地位连向瓶子的出边，也就是瓶子的入边。

剖析题意，初始的时候有 k 个环，要将其变为 n 个环，每次操作最多减少一个环，因而起码须要 n – k 次操作能力实现。

算法复杂度为 $O(n)$，因为每个点被遍历常数次。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
// 瓶子的数量
int b[N];
// 判重数组帮忙找环
bool st[N];

int main()
{scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);

    int cnt = 0;
    for (int i = 1; i <= n; i ++)
        if (!st[i])
        // 以后环没有被找过，阐明在一个新环
        {
            cnt ++ ;
            // 把这个点能达到的点都标记一下
            for (int j = i; !st[j]; j = b[j])
                st[j] = true;
        }

    printf("%d\n", n - cnt);

    return 0;
}

关于bfs:BFS算法模板与练习

模板

献给阿尔吉侬的花束

替换瓶子

暴力思路

BFS 图论思路