C语言实验作业III-迷宫（广度优先搜索）

题目：用0-1矩阵代表有无障碍，要输出一个从左上角到右下角的一个路线

Sample Input&Output

#include<stdio.h>
struct node{
    int x; //x坐标
    int y; //y坐标
    int pre; //来到此点的出发点，大概是记录这是第几个的
};
int book[6][6];  //用来记录点是否访问过
int map[6][6];   //记录图
struct node queue[20]; //存储路径的队列
void print(struct node a) //实现路径输出的函数
{
    if(a.pre==-1)
    {
        printf("(%d, %d)\n",a.x,a.y);
        return ;
    }
    else
    {
        print(queue[a.pre]);//递归调用，类似于出队的感觉，最先入队的最晚出队
        printf("(%d, %d)\n",a.x,a.y);
    }
}
int main()
{
    int i,j,k,m,n,x,y;
    int head,tail;
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {
            scanf("%d",&map[i][j]);
        }
    }
    head=0;
    tail=0;
    queue[tail].x=0;
    queue[tail].y=0;
    queue[tail].pre=-1;
    book[0][0]=1;
    tail++;//这个初始化
    while(head<tail) //当队列为空时跳出，说明搜索没有找到可行路径
    {
        int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //定义出四个方向
        int flag=0;
        for(i=0;i<4;i++)  //从当前点往四周探索
        {
            int nextx=queue[head].x+next[i][0];
            int nexty=queue[head].y+next[i][1]; //实现移动
            if(nextx<0||nextx>5||nexty<0||nexty>5) //超出了边界则跳出
            {
                continue;
            }
            if(book[nextx][nexty]==0&&map[nextx][nexty]==0) //当点未被访问过且是可行点才入队
            {
                book[nextx][nexty]=1;
                queue[tail].x=nextx;
                queue[tail].y=nexty;
                queue[tail].pre=head;
                tail++;
            }
            if(nextx==4&&nexty==4) //到达了目的地，毫无疑问地跳出结束循环
            {
                flag=1;
                break;
            }
        }
        if(flag) //到达目的地后调用函数输出路径
        {
            print(queue[tail-1]);
            break;
        }
        head++; //出队
}//到这里一直属于while循环
    return 0;
}

我认为是这样的：

1. 首先构造一个数组，这个数组储存一下每个点是不是都已经遍历过了
2. 再构建一个队列，这个结构储存每一个经过的点的位置坐标以及类似于位置这样的东西
3. 进入main函数，初始化一下：起点是肯定要经过的啦
4. 好了还是进行搜索了首先构造head和tail这两个指针（类似的），如果head和tail一头一尾追上了直接结束，这波叫做没路走了
5. tail可以向下走，那就可以走，并且把这个点的信息存储进去，
6. 假如说有两个方向有路，那就很好，tail可以加2，代表着有更多的路可以走
7. head和tail必须分别平均每次都能够+1，那就是有路的，我们可以这样理解，就是消耗与产生，tail就是产生路，head就是消耗路。每次读取head所对应的队列就是类似于找寻对应这个东西有没有路
8. 遍历完毕了，假如说找到了，那就开始输出
9. 这个时候queue的pre就可能是这样子的 -1 0 0 0 1 1 1 2 3 4 5 6 6这样的，该怎样找出适合我们的路径呢？
10. 这时候这个queue我觉得可以看成一个树，tail对应的就是节点的编号而pre对应着上一个节点的节点的编号，我们就可以进行树的遍历
11. 假如说能找到-1，也就是根节点，那可以说明我们找到了一条路了，这时候递归输出就好了