简易广搜BFS

解题思路:

左上角(0,0)坐标作为队列初始节点，

右下角(R-1,C-1)作为终点，

定义步数整型数组ArrInt并初始化所有值=未访问weight，

定义地图字符数组ArrCh来接收地图，

定义一个队列头QueHead，

定义一个结构体指针来接收新节点地址，入队列，

使用bfs思想遍历节点上下左右，

怎么查找节点

       判断数组的行列变量会不会使数组越界，会就表明可以跳过本次循环

       通过判断遍历的上下左右节点是不是    未访问weight的值&&可访问的"."

       并获取我们查找的这个节点被标记的步数StepFast值，也就是ArrInt[x][y]，将他上下左右节点的步数标记为比我们查找的节点多一步的值，并将该节点坐标存入队列

注意事项:
数组边界判断，结构体的next指针没有指向的地址就要初始化为NULL，非法输入
参考代码:

个人觉得，类似的题也可以像这样解

#include<iostream>
using namespace std;
typedef struct str {
    int R_val;
    int C_val;
    struct str *next;
} str;
int arr[4][2] = { //上下左右
    0, -1,
    0, 1,
    -1, 0,
    1, 0,
};
void InEndQue(str *in_head, str* x) {//尾插入队
    str* q = in_head;
    while (1) {
        if (q->next == NULL) {
            q->next = x;
            return;
        }
        q = q->next;
    }
}
void Free_que(str* in_head) {//释放队列所有成员
    str* q = in_head;
    str* KQ;
    while (1) {
        if (in_head->next != NULL) { //查找末尾成员的前一个
            KQ = q->next;
            q->next = q->next->next;
            free(KQ);
        } else return;
    }
}
void OneOutQue(str* in_head) {//第一个成员出队
    if (in_head->next != NULL) {
        str* Q = in_head->next;
        in_head->next = in_head->next->next;
        free(Q);
    }
}
void BFS() {
    char ch,//吃掉换行
         ArrCh[101][101]={0};//定义地图数组
    int R,//输入map size
        C,
        weight = 255,
        ArrInt[101][101] = {0};//定义步数数组
    str *QueHead = (str*)malloc(sizeof(str)), //创建队列头 并分配空间
         *Q = (str*)malloc(sizeof(str));//新节点指针
    //队列头指针初始化
    QueHead->next = NULL;
    //初始位置入队
    Q->R_val = 0;
    Q->C_val = 0;
    Q->next = NULL;
    InEndQue(QueHead, Q);
    //输入地图大小
    scanf("%d %d\n", &R, &C);
    //录入地图,初始化权值
    for (int i = 0; i < R; i++) {
        for (int ii = 0; ii < C; ii++) {
            scanf("%c", &(ArrCh[i][ii]));
            ArrInt[i][ii] = weight;//在这把步数数组初始化
        }
        scanf("%c", &ch);//吃掉换行
    }
    ArrInt[QueHead->next->R_val][QueHead->next->C_val] = 1;//初始位置的步数起始值是1 
    while (1) {//遍历开始
        int x = QueHead->next->R_val,//取出要查找的节点坐标
            y = QueHead->next->C_val,
            StepFast = ArrInt[x][y] + 1; //取出权值作为步数;
        //查找部分 根据队列成员来访问
        for (int iii = 0; iii < 4; iii++) {
            int x1 = x + arr[iii][0],
                y1 = y + arr[iii][1];
            if ((x1 < 0) | (y1 < 0) | (x1 > R) | (y1 > C))continue; //边界判断
            if (ArrInt[x1][y1] == weight && ArrCh[x1][y1] == '.') { //访问未访问
                //赋权图最短步数
                if (x1 == R - 1 && y1 == C - 1) {
                        ArrInt[x1][y1] = StepFast;
                        cout << StepFast;
                        Free_que(QueHead);//队列头的空间并没有释放
                        free(QueHead);
                        QueHead = NULL;
                        return;//终点
                    } else {
                        ArrInt[x1][y1] = StepFast;
                    }
                    //节点入队
                    Q = (str*)malloc(sizeof(str));
                    Q->next = NULL;
                    Q->R_val = x1;
                    Q->C_val = y1;
                    InEndQue(QueHead, Q);
                }
        }
        //删除查找完了的这个节点
        OneOutQue(QueHead);
    }
 
}
int main() {
    BFS();
}