最近才把之前放下的数据结构捡起来，就以宽搜来开头吧

~~摆烂两个月，我是小丑~~

广度优先搜索（Breadth First Search）
- 介绍
  就不细说了，详见
  
  广度优先搜索（BFS）算法详解 (biancheng.net)
  
  BFS——广度优先算法（Breadth First Search）_sooner高的博客-CSDN博客_bfs
- 总结
  一般来说，求从一个状态到另一个状态所需的最少变换次数，使用BFS

迷宫

题目

一个入口，一个出口，有边界，有墙阻挡，求最短路径

这里就以6x6的地图大小了

用**#表示墙，0**为可走，黄色表示起点和终点

输入地图、起点坐标、终点坐标

Sample Input

##0###
##0#0#
#0000#
#0#0##
#0000#
####0#
1 3 6 5

Sample Output
1
7

参考代码

#include <bits/stdc++.h>
#define N 100
using namespace std;
/*
##0###
##0#0#
#0000#
#0#0##
#0000#
####0#
*/
char ditu[N][N];
int flag[N][N] = {0}; //记录状态
typedef struct
{
    int x;
    int y;
    int step;
}POINT;
queue<POINT> q;//队列
int go[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//上下左右
int start_x,start_y,end_x,end_y;
int res;
int area=6;//地图大小 就按6*6了

void bfs()
{
    //先把初始状态 入队 再 出队
    POINT startp;
    startp.x = start_x;
    startp.y = start_y;
    startp.step = 0;
    q.push(startp);

    while(!q.empty())//队列不为空一直执行
    {
        POINT headp = q.front(); //取当前队列的头给临时变量
        q.pop();//出队 拓展
        for(int i=0; i<4; i++)
        {
            int new_x = headp.x + go[i][0];
            int new_y = headp.y + go[i][1];//上下左右拓展
            if(flag[new_x][new_y] || new_x < 1 || new_y < 1 || new_x > area || new_y > area || ditu[new_x][new_y]) //是否到达过 边界 墙
                continue;
            flag[new_x][new_y] = 1;
            POINT joinp;
            joinp.x = new_x;
            joinp.y = new_y;
            joinp.step = headp.step + 1;
            if(new_x == end_x && new_y == end_y)//判断是否结束
            {
                res = joinp.step;
            }
            q.push(joinp);//入队 继续
        }
    }
}

int main()
{
    char trs;//临时变量转换
    for(int i=1; i<=area; i++)
    {
        for(int j=1; j<=area; j++)
        {
            cin >> trs;
            if(trs == '#')
                ditu[i][j] = 1;
            else
                ditu[i][j] = 0;
        }
    }
    cin >> start_x >> start_y >> end_x >> end_y;
    bfs();
    cout << res;
    return 0;
}

奇怪的电梯

https://www.luogu.com.cn/problem/P1135

题目描述

输入格式

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

样例输入

1 2	5 1 5 3 3 1 2 5

样例输出

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int start_f,end_f;
int N;
int flr[201];//记录每一楼层上对应的次数
int flag[201];//标记状态
int res = -1;//找不到输出-1

typedef struct//定义一个结构体 表示当前楼层和按钮次数
{
    int loc;
    int step;
}POINT;
queue<POINT> q;

void bfs()
{
    POINT ST;
    ST.loc = start_f;
    ST.step = 0;
    q.push(ST);//常规流程 入队 出队
    while(!q.empty())
    {
        POINT STHead = q.front();//临时变量 存当前队头
        q.pop();
        int newu,newd;
        newu = STHead.loc + flr[STHead.loc];//向上移动的层数
        newd = STHead.loc - flr[STHead.loc];//向下移动的层数
        POINT JOIN;//临时变量 用来保存可行的状态
        if(flag[newu]==-1 && newu <= N)
        {
            JOIN.loc = newu;
            JOIN.step = STHead.step + 1;
            flag[newu]=0;//记录到达过
            q.push(JOIN);
            if(JOIN.loc == end_f)
            {
                if(res==-1)
                {
                    res = JOIN.step;//找到最少次数
                    continue;
                }
            }
        }
        if(flag[newd]==-1 && newd >= 1)
        {
            JOIN.loc = newd;
            JOIN.step = STHead.step + 1;
            flag[newd]=0;//记录到达过
            q.push(JOIN);
            if(JOIN.loc == end_f)
            {
                if(res==-1)
                {
                    res = JOIN.step;//找到最少次数
                    continue;
                }
            }
        }
    }
}

int main()
{
    cin >> N >> start_f >> end_f;
    for(int i=1;i<=N;i++)
    {
        cin >> flr[i];//读取对应楼层编号
    }
    memset(flag,-1,sizeof(flag));//初始化
    //flag[start_f] = 0;
    if(start_f == end_f)//如果初始楼层和要到达楼层为同一层 则直接输出
    {
        res = 0;
    }
    bfs();
    cout << res << endl;
    return 0;
}