NO.74十六届蓝桥杯备战|搜索算法-BFS|马的遍历|迷宫|Catch That Cow|八数码难题(C++)

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

P1443 马的遍历 - 洛谷

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

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 410;

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

int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {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.size())
    {
        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) continue;
            if (dist[x][y] != -1) continue;

            dist[x][y] = dist[i][j] + 1; //更新结果
            q.push({x, y});
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    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;
}

迷宫

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

#include <bits/stdc++.h>
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[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs()
{
    memset(dist, -1, sizeof dist);
    queue<PII> q;
    q.push({x, y});
    dist[x][y] = 0;
    
    while (q.size())
    {
        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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    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 cnt = 0, ret = 1e9;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 'e' && dist[i][j] != -1)
            {
                cnt++;
                ret = min(ret, dist[i][j]);
            }
        }
    }
    if (cnt == 0) cout << -1 << endl;
    else cout << cnt << " " << ret << endl;
    
    return 0;
}

P1588 [USACO07OPEN] Catch That Cow S - 洛谷

可以暴⼒枚举出所有的⾏⾛路径，因为是求最少步数，所以可以⽤bfs解决：

• 从起点位置开始搜索，每次向外扩展三种⾏⾛⽅式；
• 当第⼀次搜到⽜的位置时，就是最短距离。
  如果不做任何处理，时间和空间都会超。因为我们会搜索到很多⽆效的位置，所以我们要加上剪枝策略：

1. 当-1 减到负数的时候，剪掉；
   因为如果⾛到负数位置，还是需要回头⾛到正数位置，⼀定不是最优解。
2. 当+1 操作越过y 的时候，剪掉；
   如果+1之后⼤于y，说明本⾝就在y位置或者y的右侧，你再往右⾛还是需要再向左⾛回去。⼀定不是最优解，剪掉。
3. 当y 是偶数，并且当×2 操作之后⼤于y 的时候，剪掉，因为不如先减到y 的⼀半然后再乘；
   设当前数是x ，那么：

• 先乘后减，总的步数t1 = 2x - y + 1 ；
• 先减后乘，总的步数t2 = x - y/2 + 1 ；
• t1 - t2 = 2x - y + 1 - (x - y/2 + 1) = x - y/2 > 0 ；
• 因此，先乘后减不如先减后乘

4. 设y 是奇数的时候，那么y + 1 就是偶数，根据3 可得，×2 操作不能超过y + 1

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int n = 1e5;
int x, y;
int dist[N];

void bfs()
{
    queue<int> q;
    q.push(x);
    dist[x] = 0;

    while (q.size())
    {
        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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;
    while (T--)
    {
        //清空数据
        memset(dist, -1, sizeof dist);

        cin >> x >> y;
        bfs();
        cout << dist[y] << endl;
    }
    
    return 0;
}

P1379 八数码难题 - 洛谷

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

• 从起始状态开始，每次扩展上下左右交换后的状态；
• 在搜索的过程中，第⼀次遇到最终状态就返回最短步数。
  算法原理虽然容易，但是实现起来⽐较⿇烦，我们要想办法处理下⾯⼏件事情：

1. 如何记录⼀个3 × 3 的棋盘？
   可以⽤字符串。从上往下，从左往右将棋盘内的数依次存到⼀个字符串⾥，来标记棋盘的状态。
2. 如何记录最短路？
   可以⽤unordered_map <string, int> 来标记最短距离；
3. 如何通过⼀个字符串找到交换之后的字符串？
   策略⼀：先把字符串还原成⼆维矩阵，然后交换0与四周的数字，最后再把交换之后的棋盘还原
   成字符串。
   虽然可⾏，但是太过于⿇烦。我们其实可以通过计算，快速得出⼆维坐标与⼀维下标相互转换前后的值。如下图

1. 二维坐标(x,y) --> 一维下标(pos)：pos = x * 3 + y
2. 一维下标(pos)–> 二维坐标(x,y) ：x = pos / 3; y = pos % 3;
   这个技巧特别常⽤，我们可以推⼴到nxm的矩阵坐标(x,y)，映射成⼀个数pos，可以起到空间优化的效果。后续做题中我们就会遇到。
   因此，我们可以直接在字符串中，找出交换前后的下标，直接交换字符串对应位置，就能得到交换之后的状态。

#include <bits/stdc++.h>
using namespace std;

string s;
string aim = "123804765";
unordered_map<string, int> dist;

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

void bfs()
{
    queue<string> q;
    q.push(s);
    dist[s] = 0;

    while (q.size())
    {
        string t = q.front(); q.pop();

        int pos = 0; 
        while (t[pos] != '0') pos++;
        int x = pos / 3, y = pos % 3;  //计算二维位置
        
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a <= 2 && b >= 0 && b <= 2)
            {
                string next = t;
                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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;

    bfs();

    cout << dist[aim] << endl;
    
    return 0;
}