Caioj 1047: 魔板

二维魔方，全是套路

题目

---

题目链接: [http://caioj.cn/problem.php?id=1047]

二维的魔方貌似并没有比三维的魔方简单到哪里 我们可以看出，这道题是一个搜索，并且求的是最优解，也就是宽搜的事了 然后再让我们想想哈希表的问题，首先我们知道只有八个数，并且还都是 1-8 ,显然就应该用康托展开了

部分代码 & 想法

---

我们要对这一串数字进行处理，显然是应当以数组方式存的（当然你也可以存成整数操作，如果你不觉得累的话），我们要输出操作，这是这道题中的一个大坑=.=，显然我们将操作以字符串的形式存起来内存会非常大，所以我们应当换一种方法. 我们知道，每中搜索都会有一颗对应的搜索树，以这个为基础，我们就可以想到，将他的父节点存下来，只在当前的结构体中存我们从父节点过来的操作，然后在输出时一路递归回到根节点，再逆序输出即可。 结构体:

struct node{
    int deep,a[3][5],k,last;
    char d;
}b[400000],ed;

deep – 当前深度(步数） a[][] – 当前魔板的状况 k – 康托展开 last – 父亲节点 d – 从父节点过来的操作 输出操作:

void sc2(int k){
    if(b[k].last!=-1) sc2(b[k].last);
    if(b[k].last!=-1) printf("%c",b[k].d);
    return ;
}

然后就是广搜的基本套路=.=，大家都会写的说

部分小坑

---

1. 这个魔板是在第二列是从右往左读入的
2. 别忘记输出 no !
3. 处理时谨慎点

]]>