啊哈，算法自学记——7th

小哈迷宫搜救记之——

广度优先搜索

#include <stdio.h>

typedef struct note
{
    int x;
    int y;
    int step;
};


int main(int argc, char const *argv[])
{
    struct note que[2501];//因为地图大小不会超过50*50，所以地图扩展不过超过2500
    int a[51][51]={0};//存储地图
    int book[51][51]={0};//标记已经走过的路线

    int next[4][2]={
        {0,+1},//you
        {+1,0},//xia
        {0,-1},//zuo
        {-1,0}//shang
    };

    int head,tail;
    int n,m,flag,xstart,ystart,p,q,tx,ty;

    printf("Read The Map:
");
    printf("Input the size of the map:
");
    scanf("%d %d",&n,&m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    
    printf("Input the xstart ystart and xend yend:
");
    scanf("%d %d %d %d",&xstart,&ystart,&p,&q);

    //队列初始化
    head=1;
    tail=1;
    //往队列中插入地图入口坐标
    que[tail].x=xstart;
    que[tail].y=ystart;
    que[tail].step=0;
    tail++;
    book[xstart][ystart]=1;//标记起点已在路径中

    flag=0;//表示暂时没有到达目标点

    //当队列不为空的时候循环
    while (tail>head)
    {
        for (int i = 0; i <= 3; i++)
        {
            //计算下一个点的坐标
            tx=que[head].x+next[i][0];
            ty=que[head].y+next[i][1];

            //判断是否越界
            if(tx<1||ty<1||tx>n||ty>m)
                continue;
            //判断是否是障碍物或者已经在路径之中
            if(a[tx][ty]==0 && book[tx][ty]==0)
            {
                //标记该点已经走过
                book[tx][ty]=1;
                //插入新的点到队列中去
                que[tail].x=tx;
                que[tail].y=ty;
                que[tail].step=que[head].step+1;
                tail++;
            }

            if (tx==p && ty==q)
            {
                flag=1;
                break;
            }
            
        }
        
        if (flag==1)
        {
            break;
        }
        head++;//当一个点扩展结束后，head++才能对后面的点进行扩展
    }
    

    printf("%d",que[tail-1].step);

    return 0;
}