当前位置：首页 > article >正文

【算法】BFS

article 2025/1/29 8:02:44

BFS

1.马的遍历
2.kotori和迷宫
3.Catch That Cow
4.八数码难题

宽度优先搜索的过程中，每次都会从当前点向外扩展一层，所以会具有一个最短路的特性。因此，宽搜不仅能搜到所有的状态，而且还能找出起始状态距离某个状态的最小步数。
但是，前提条件是每次扩展的代价都是 1，或者都是相同的数。宽搜常常被用于解决边权为 1 的最短路问题。

1.马的遍历

P1443 马的遍历

在这里插入图片描述

解法：BFS

题目要求到达某个点最少要走几步，因此可以用 BFS 解决。因为当权值为 1 时，BFS 每次都是扩展距离起点等距离的一层，天然具有最短性。那就从起点开始，一层一层的往外搜，用一个 dist 数组记录最短距离。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 410;

int n, m, x, y;
int dist[N][N]; //最短路数组

//马行走的八个方向
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

void bfs()
{
	memset(dist, -1, sizeof(dist));
	
    queue<PII> q;
    q.push({x, y});
    dist[x][y] = 0;
    
    while(!q.empty())
    {
        auto t = q.front(); q.pop();
        int i = t.first, j = t.second;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            
            //未越界 + 该坐标没有遍历过
            if(x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y] == -1)
            {
                q.push({x, y});
                dist[x][y] = dist[i][j] + 1; //更新结果
            }
        }
    }
}

int main()
{
    cin >> n >> m >> x >> y;
    
    bfs();
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

2.kotori和迷宫

kotori和迷宫

在这里插入图片描述

解法：BFS

经典 bfs 问题。从迷宫的起点位置逐层开始搜索，每搜到一个点就标记一下最短距离。当把整个迷宫全部搜索完毕之后，扫描整个标记数组，求出出口的数量以及最短的距离。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 35;

int n, m, x, y;
char a[N][N];
int dist[N][N];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs()
{
    memset(dist, -1, sizeof(dist));
    
    queue<PII> q;
    q.push({x, y});
    dist[x][y] = 0;
    
    while(!q.empty())
    {
        auto t = q.front(); q.pop();
        int i = t.first, j = t.second;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '*' && dist[x][y] == -1)
            {
                dist[x][y] = dist[i][j] + 1;
                if(a[x][y] == 'e') continue; //遇到迷宫出口时：不需要入队
                q.push({x, y});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'k') //找出迷宫的入口
            {
                x = i;
                y = j;
            }
        }
    }
    
    bfs();
    
    int ret = 1e9, cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j] == 'e' && dist[i][j] != -1)
            {
                ret = min(ret, dist[i][j]);
                cnt++;
            }
        }
    }
    
    if(cnt == 0) cout << -1 << endl;
    else cout << cnt << " " << ret << endl;
}

3.Catch That Cow

P1588 [USACO07OPEN] Catch That Cow S

在这里插入图片描述

解法：BFS

可以暴力枚举出所有的行走路径，因为是求最少步数，所以可以用 bfs 解决：

从起点位置开始搜索，每次向外扩展三种行走方式。
当第一次搜到牛的位置时，就是最短距离。

如果不做任何处理，时间和空间都会超。因为我们会搜索到很多无效的位置，所以我们要加上剪枝策略：

当 −1 减到负数的时候，剪掉。因为如果走到负数位置，还是需要回头走到正数位置，一定不是最优解。
当 +1 操作越过 y 的时候，剪掉。因为如果 +1 之后大于 y，说明本身就在 y 位置或者 y 的右侧，你再往右走还是需要再向左走回去。一定不是最优解，剪掉。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;

int n = 1e5;

int x, y;
int dist[N];

void bfs()
{
    queue<int> q;
    q.push(x);
    dist[x] = 0;
    
    while(!q.empty())
    {
        auto t = q.front(); q.pop();
        int a = t + 1, b = t - 1, c = t * 2;
        
        if(a <= n && dist[a] == -1)
        {
            dist[a] = dist[t] + 1;
            q.push(a);
        }
        
        if(b > 0 && dist[b] == -1)
        {
            dist[b] = dist[t] + 1;
            q.push(b);
        }
        
        if(c <= n && dist[c] == -1)
        {
            dist[c] = dist[t] + 1;
            q.push(c);
        }
        
        if(a == y || b == y || c == y) return; //到达终点时：就是最短路
    }
}

int main()
{
    int T; cin >> T;
    while(T--)
    {
        //注意清空数据
        memset(dist, -1, sizeof(dist));
        cin >> x >> y;
        bfs();
        cout << dist[y] << endl;
    }
    
    return 0;
}

4.八数码难题

P1379 八数码难题

在这里插入图片描述

解法：BFS

经过之前那么多题的铺垫，这道题的解法还是容易想到的。因为要求的是最短步数，因此可以用 bfs 解决。

从起始状态开始，每次扩展上下左右交换后的状态。
在搜索的过程中，第一次遇到最终状态就返回最短步数。

算法原理虽然容易，但是实现起来比较麻烦，我们要想办法处理下面几件事情：

如何记录一个 3 × 3 的棋盘？可以用字符串。从上往下，从左往右将棋盘内的数依次存到一个字符串里，来标记棋盘的状态。
如何记录最短路？可以用 unordered_map<string, int> 来标记最短距离。
如何通过一个字符串找到交换之后的字符串？

策略一：先把字符串还原成二维矩阵，然后交换与四周的数字，最后再把交换之后的棋盘还原成字符串。虽然可行，但是太过于麻烦。我们其实可以通过计算，快速得出二维坐标与一维下标相互转换前后的值。如下图：

在这里插入图片描述

这个技巧特别常用，我们可以推广到 n × m 的矩阵坐标 (x, y)，映射成一个数 pos，可以起到空间优化的效果。后续做题中我们就会遇到。因此，我们可以直接在字符串中，找出交换前后的下标，直接交换字符串对应位置，就能得到交换之后的状态。

#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>
using namespace std;

string s; 
string aim = "123804765";
unordered_map<string, int> dist; //存储输入的字符串s到达某个字符串的最短路

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs()
{
    queue<string> q;
    q.push(s);
    dist[s] = 0;
    
    while(!q.empty())
    {
        string t = q.front(); q.pop();
        
        int pos = 0;
        while(t[pos] != '0') pos++; //找到一维空间字符0的坐标
        int x = pos / 3, y = pos % 3; //将一维转换为二维后字符0的坐标
        
        for(int k = 0; k < 4; k++)
        {
            int a = x + dx[k], b = y + dy[k];
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                string next = t; //防止修改
                
                //(x, y) 与 (a, b) 进行交换
                int p = 3 * a + b; //本质是转换为一维坐标进行交换
                swap(next[p], next[pos]);
                if(dist.count(next)) continue; //注意: 若存在, 跳过即可
                
                dist[next] = dist[t] + 1;
                q.push(next);
                
                if(next == aim) return; //找到的第一个就是最短路, 结束递归
            }
        }
    }
}

int main()
{
    cin >> s;
    bfs();
    cout << dist[aim] << endl;
    
    return 0;
}