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. 处理时谨慎点
]]>

发表评论

电子邮件地址不会被公开。 必填项已用*标注