标签：数码

广搜入门题，经典八数码 题库中已经说的很清楚了，这题是用广搜（又称宽搜），那么，何为宽搜，它与深搜区别何在？

1.深搜与广搜

---

这两种搜索的全名分别是: 深搜——深度优先搜索 广搜——广度优先搜索 其英文缩写分别是 dfs 与 bfs ,虽然只差一个字母，不过却有所不同 深搜的特点是短而难想 广搜的特点是长且难写 我们就根据八数码这道题，说一下深搜与广搜的区别，先看看下面这张图:

                  0
           /   |    |   \
        上 下 左  右(最优解）
    /  |    |    \
上 下 左 右（次右解）

如果你是用深搜他会这么寻找: 0->上->上->返回上一层->下->返回上一层->左->返回上一层->右(次优解）->返回上一层->下-》……最优解 然而广搜是这个样子的 0->上->下->左->右(最优解）->进入下一层-》上-》下-》左-》右-》次优解 以上应该就可以很明白的看出，深搜是将一步搜索到底再回头，广搜是在每一层搜索，所以广搜第一个搜到的一定是最优解。 不过为什么会右这样的差距，这就要看广搜的原理了

2.何为广搜

---

广度优先搜索

这不就是没解释 也就是说我们先把同一个步数的所有情况扩展完，然后进行判断，这也就是为什么第一个答案就是最优解 我们说这种情况，每一种情况搜完就不在需要了，而最近被搜到的应该放入最后，也就是说，先进先出——队列 那也就是说，这个东西需要我们开队列=.=，并且这种状况下，重复的可能性很高，关于如何这道题的剪枝方法，你可以看看这个 Caioj 1220:康托展开和康托展开的逆运算

3.题目&思路&部分代码

---

题目链接: http://caioj.cn/problem.php?id=1046

首先我们知道，这个题我们就是要模拟上下左右，也就是说我们读入初始与截止情况，将初始情况放入队列首，先来看看队列怎么写吧

struct FUCK{
    int a[4][4],x,y,deep;
}dl[400000],ed;

请忽略结构体名 dl[] 也就是队列

• int a[][] 临时储存数码图
• x,y 0 的坐标
• deep 深度，也就是步数

ed 结尾情况 嗯对就是这样 然后就是判断重复，也就是上文所说的康托展开，我们吧每一中情况打成哈希表（坑爹玩意）,然后就可以判断重复了，接下来就可以进行搜索

    while(l<=r){
        for(int i=0;i<4;i++){
            FUCK fir=dl[l];
            fir.x=dl[l].x+dx[i];
            fir.y=dl[l].y+dy[i];
            if(fir.x>=1&&fir.x<=3&&fir.y>=1&&fir.y<=3){
                int temp=fir.a[fir.x][fir.y];
                fir.a[fir.x][fir.y]=fir.a[dl[l].x][dl[l].y];
                fir.a[dl[l].x][dl[l].y]=temp;
                int temp_kt=zys(fir);
                fir.deep=dl[l].deep+1;
                if(!xd[temp_kt]){
                    xd[temp_kt]=true;
                    r++;
                    dl[r]=fir;
                    if(temp_kt==z){
                        printf("%d\n",fir.deep);
                        return 0;
                    }
                }
            }
        }
        l++;
    }

其中 l 是队列首指针， r 是队列尾指针, for 循环对应的就是 dx[] , dy[] 这两个增量然后我们就交换变量， 随意说这道题并不是特别的难 当然如果你不加判断重复就会 RE 了2333 ]]>