(BFS) Breadth-First Search入门

广度优先搜索:BFS全称Breadth First Search. 广度优先，优先在于广度，尽量的往周围扩散再前进。 如果是DFS是一只迷宫里的蚂蚁，那么BFS就像倒在地上的一滩水. BFS的搜索是蔓延式的进行. 观察下列，搜索是从(1,1)开始的 搜索的优先级为右下左上 每个数字代表是第几个被搜索到的 1 2 4 7 11 3 5 8 12 16 6 9 13 17 20 10 14 18 21 23 15 19 22 24 25 可以观察到我们的搜索是如水一般蔓延开来的，按照我们设置好的搜索规则依次判断. 我们设置了一个边长为5X5的图,且初始点我们让其从(1,1)开始进行. 过程的简单描述: 从(1,1)开始,先判断右边是否走过,没走过将其标为2. 然后再回到(1,1)接着判断下面是否走过，没走过将其标为3. 然后判断左边，为边界无法走，接着判断上面，为边界无法走. (1,1)此时4个方位都判断完了，接着来到(1,1)这个点判断标记的第一个点———(1,2) 然后从(1,2)开始刚刚的过程,最终形成了这个图.

题目:快乐的马里奥 这是一个基础的bfs题,题解思路如我们上述相同. 用代码怎么实现呢？ 我们需要用到核心为 queue 和 pair 使用队列的特性---先进先出，记录最先标记了的坐标位置,下面给出AC代码

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
int main()
{
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int m, n; cin >> m >> n;//输入行列
    vector<vector <int> >v( m + 1,vector<int> ( n + 1, 0 ));//设置二维数组
    queue<pair<int,int> >q;//队列用来记录坐标
    q.push({1,1});//设置初始的坐标，也是开始的坐标
    v[1][1] = 1;//对初始点赋初值
    int cnt = 2;//因为初始点为1,第二个点从2开始
    while(!q.empty()){//队列存储的坐标不为空就执行
      //取出队列中存储的第一个坐标，用完就丢
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
      //依次判断四个方位
        for(int i = 0;i < 4;i++){
            int nx = x + fx[i];
            int ny = y + fy[i];
            if(nx <= m && nx > 0 && ny <= n && ny > 0 && v[nx][ny] == 0){
                v[nx][ny] = cnt++;//赋值标记
                q.push({nx,ny});//将赋值点的坐标存入队列
            }
        }
    }
        //打印输出
    for(int i = 1; i <= m;i++){
        for(int j = 1; j <= n;j++){
            cout << v[i][j] << " ";
        }
        cout << '\n';
    }

    return 0;
}