【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面：

题目：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输入只有一行四个整数，分别为n, m, x, y。

输出格式：

一个 n × m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

输入样例：

3 3 1 1

输出样例：


输出 #1复制
0    3    2    
3    -1   1    
2    1    4

解题思路：

我们根据这道题的数据范围，可以判断出，

这道题需要使用广度优先搜索，题目要求是，

找出马到一个点最少需要几步，

我们用bfs，一层层搜索他的情况即可，

那么我们先来模拟一下题目给出的用例：

这个是我们的起点：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

在象棋中，马走日字，在这个矩阵中，

它有两个位置可以走：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

所以那两个位置被置为1，

表明马已经走了一步，

我们让马继续走：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

马有走到这些位置，

继续记录路径和：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

马继续走，以此类推，最后就会走到目标点位：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

我们根据上面的规律实现代码，

但是这一次，我打算换一种方式，

因为调用STL库中的队列速度是比较慢的，

我们可以自己用数组模拟一个队列，

这样可以加快效率，

我们应该怎么实现呢？

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

我们可以用头尾两个指针维护这个队列，

往队列插入一个数：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

如果要出队，那就让队头++，

这样就访问不了那个数了：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

如果要入队，

就让队尾 tail++，再q[tail] = x。

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

如果队头大于队尾，那就证明队列为空：

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

下面是代码实现：

代码：

//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m, x, y;

const int N = 500;

//存坐标
typedef pair<int, int> PII;

//存马的步数
int dist[N][N];

//用数组模拟队列
PII q[N * N];

//存坐标偏移量
int dx[] = {2, 2, 1, 1, -1, -1, -2, -2};
int dy[] = {1, -1, 2, -2, 2, -2, 1, -1};

void bfs(int x, int y)
{
    //初始化
    memset(dist, -1, sizeof(dist));
    
    //插入第一个数据
    q[0] = {x, y};
    dist[x][y] = 0;
    int head = 0;
    int tail = 0;
    
    //如果头指针大于尾指针，证明队列为空
    while(head <= tail)
    {
        auto t = q[head];
        head++;
        for(int i = 0; i < 8; i++)
        {
            int a = dx[i] + t.first;
            int b = dy[i] + t.second;
            
            //控边界
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(dist[a][b] >= 0) continue;
            
            //记录马的步数
            dist[a][b] = dist[t.first][t.second] + 1;
            
            //入队
            tail++;
            q[tail] = {a, b};   
        }
    }
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &x, &y);
    bfs(x, y);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            printf("%-5d", dist[i][j]);
        }
        printf("\n");
    }
    return 0;
}