万能的搜索的学习——广度优先搜索

广度优先搜索是最简便的图的搜索算法之一，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先是从一个方向一直尝试下去，直到走不通的时候在回到原来地方继续寻找。而广度优先是通过“一层一层”扩展的方法去寻找目标。扩展时每发现一个点就将这个点加入到队列中，直到找到目标为止。

例如下面这道题，从起点到达终点需要几步？

最开始从入口（1，1）处，一步之内可以到达的点有（1，2）和（2，1），但是终点并不在这两个点上，那只能通过（1，2）和（2，1）这两点继续往下走，那么两步之内能到达哪些点呢？只有（2，2）和（3，1），为了防止一个点多次被走到，这里需要一个数组来记录一个点是否已经走过。

此时两步到达的点事（2，2）和（3，1），可惜终点并不是这两点，所以还要继续往下走，三步能到的点是（2，3）、（3，2）和（4，1），依旧不是终点，所以需要重复刚才的方法，直到找终点为止。
完整代码如下：

#include <stdio.h>

struct note {
    int x;  //横坐标
    int y;  //纵坐标
    int s;  //步数
};

int main(int argc, const char * argv[]) {
    
    struct note que[17];    //应为地图大小不超过 4X4，因此队列扩展不会超过16个
    
    // 记录走过的点，和标记
    int a[5][5] = {0},mark[5][5]= {0};
    
    // 定义一个用于表示走的方向的数组
    int next[4][2] = {{0,1}, // 向右走
                      {1,0}, // 下
                      {0,-1},// 左
                      {-1,0} // 上
                        };
    
    int head,tail;
    int k,tx,ty,flag;
    
    //队列初始化
    head = 1;
    tail = 1;
    //往队列插入迷宫入口坐标
    que[tail].x = 1;
    que[tail].y = 1;
    que[tail].s = 0;
    tail++;
    mark[1][1] = 1; //起点已经走过
    
    // 用来标记是否到达目标点，0表示暂时还没有到达，1表示到达
    flag = 0;
    // 当队列不为空的时候循环
    while (head < tail) {
        // 枚举4个方向
        for (k = 0; k <= 3; k++) {
            
            // 计算下一个点的坐标
            tx = que[tail].x + next[k][0];
            ty = que[tail].y + next[k][1];
            
            // 判断是否越界
            if (tx <1 || tx >5 || ty <1 || ty >4) continue;
            // 判断是否是障碍物或者已经在路径中
            if (a[tx][ty] == 0 && mark[tx][ty] == 0) {
                
                // 把这个点标记为已经走过，每个点只入队一次
                mark[tx][ty] = 1;
                // 插入新的点到队列中
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].s = que[head].s +1;   // 步数加1
                tail++;
                
            }
            
            // 如果找到目标点，停止扩展，任务结束，退出循环
            if (tx == 4 && ty == 3) {
                flag = 1;
                break;
            }
        }
        if (flag == 1) {
            break;
        }
        // 当一个点扩展结束后，head++才能对后面的点再进行扩展
        head++;
    }
    // tail是指向队列队尾的下一个位置，所以需要-1
    printf("%d",que[tail -1].s);
    
    getchar();getchar();
    return 0;
}