关键词:
题目背景
在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:
1 2 3 4
8 7 6 5
题目描述
我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。对于上图的魔板状态,我们用序列(1,2,3,4,5,6,7,8)来表示。这是基本状态。
这里提供三种基本操作,分别用大写字母“A”,“B”,“C”来表示(可以通过这些操作改变魔板的状态):
“A”:交换上下两行;
“B”:将最右边的一列插入最左边;
“C”:魔板中央四格作顺时针旋转。
下面是对基本状态进行操作的示范:
A: 8 7 6 5
1 2 3 4
B: 4 1 2 3
5 8 7 6
C: 1 7 2 4
8 6 3 5
对于每种可能的状态,这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到目标状态的转换,输出基本操作序列。
输入输出格式
输入格式:
只有一行,包括8个整数,用空格分开(这些整数在范围 1——8 之间)不换行,表示目标状态。
输出格式:
Line 1: 包括一个整数,表示最短操作序列的长度。
Line 2: 在字典序中最早出现的操作序列,用字符串表示,除最后一行外,每行输出60个字符。
输入输出样例
2 6 8 4 5 7 3 1
7 BCABCCB
说明
题目翻译来自NOCOW。
USACO Training Section 3.2
/* 八数码难题那种搜索做多了,这种题也就不叫题了。。 直接宽搜,记录状态直接map(hash害我无数次我才不要用),字符串直接加加减减拼组起来,我以为会超时呢。 就是这么暴力的方法,主意一下内存限制,队列不要开得太大,当然循环队列这里用不到。 在注意一下输出格式,就可以A了。 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> using namespace std; map<string,bool>vis; struct node{ int fa,step; string s; char op; }cur,nxt,q[5000000]; int head=1,tail=0; string goal,start="12348765",ans; void work(int now){ if(q[now].fa==-1)return; work(q[now].fa); //printf("%c",q[now].op); ans+=q[now].op; } int main(){ //freopen("Cola.txt","r",stdin); int x; string ch; for(int i=1;i<=8;i++){ scanf("%d",&x); ch+=x+‘0‘; } goal+=ch.substr(0,4); for(int i=7;i>=4;i--)goal+=ch[i]; cur.s=start;cur.fa=-1;cur.step=0; vis[cur.s]=1; if(cur.s==goal){ printf("0"); return 0; } q[++tail]=cur; while(head<=tail){ cur=q[head]; string s=cur.s; if(cur.s==goal){ printf("%d ",cur.step); work(head); int start=0,len=ans.length(); while(start<len){ cout<<ans.substr(start,60); start+=60; } break; } //操作A nxt.s=""; nxt.s+=s.substr(4,4);nxt.s+=s.substr(0,4); nxt.op=‘A‘;nxt.step=cur.step+1;nxt.fa=head; if(!vis[nxt.s])q[++tail]=nxt,vis[nxt.s]=1; if(nxt.s==goal){ printf("%d ",nxt.step); work(tail); int start=0,len=ans.length(); while(start<len){ cout<<ans.substr(start,60); start+=60; } break; } //操作B nxt.s=""; nxt.s+=s[3];nxt.s+=s.substr(0,3); nxt.s+=s[7];nxt.s+=s.substr(4,3); nxt.op=‘B‘;nxt.step=cur.step+1;nxt.fa=head; if(!vis[nxt.s])q[++tail]=nxt,vis[nxt.s]=1; if(nxt.s==goal){ printf("%d ",nxt.step); work(tail); int start=0,len=ans.length(); while(start<len){ cout<<ans.substr(start,60); start+=60; } break; } //操作C nxt.s=""; nxt.s+=s[0];nxt.s+=s[5];nxt.s+=s[1];nxt.s+=s[3];nxt.s+=s[4];nxt.s+=s[6];nxt.s+=s[2];nxt.s+=s[7]; nxt.step=cur.step+1;nxt.op=‘C‘;nxt.fa=head; if(!vis[nxt.s])q[++tail]=nxt,vis[nxt.s]=1; if(nxt.s==goal){ printf("%d ",nxt.step); work(tail); int start=0,len=ans.length(); while(start<len){ cout<<ans.substr(start,60); start+=60; } break; } head++; } /*int sz=sizeof(q)+sizeof(vis); cout<<endl<<sz/1048576;*/ }
p2730魔板magicsquares(代码片段)
题意:初始魔板1234 8765三种操作“A”:交换上下两行;“B”:将最右边的一列插入最左边;“C”:魔板中央四格作顺时针旋转。下面是对基本状态进行操作的示范:A:8765 1 234B:4123 5876C:172... 查看详情
p2730魔板magicsquares(代码片段)
没看过题的童鞋请去看一下题-->P2730魔板MagicSquares不了解康托展开的请来这里-->我这里至于这题为什么可以用康托展开?(瞎说时间到.因为只有8个数字,且只有1~8这8个数字,所以我们可以算出最多情况有8!=40320个.所以我们完全... 查看详情
luogup2730魔板magicsquares(代码片段)
P2730魔板MagicSquares题目背景在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:12348765题目描述我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表... 查看详情
魔板magicsquares(代码片段)
【题目描述】:魔板MagicSquares【思路】:是不是感觉和八数码有点像?显而易见的宽搜,把魔板的状态表示为排列,则状态最多有(8!=40320)种,空间是可以接受的,对于是第几个排列可以用康拓展开来实现(我想在做八数码的时... 查看详情
魔板magicsquares(广搜,状态转化)(代码片段)
题目背景在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:12348765题目描述我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的... 查看详情
神器的方块magicsquares
题目背景在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:12348765题目描述我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的... 查看详情
题解lgp2730魔板magicsquares(代码片段)
【题目背景】在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:12348765【题目描述】我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以... 查看详情
洛谷p1275魔板
P1275魔板题目描述有这样一种魔板:它是一个长方形的面板,被划分成n行m列的n*m个方格。每个方格内有一个小灯泡,灯泡的状态有两种(亮或暗)。我们可以通过若干操作使魔板从一个状态改变为另一个状态。操作的方式有两种:... 查看详情
magicsquares(代码片段)
要求1:在MagicSquqre.java文件中添加isLegalMagicSquare()函数,判断一个矩阵是否为MagicSquare。MagicSquare说明:矩阵行数以及列数相同,且每行元素之和,每列元素之和以及对角线元素之和都应相等: ... 查看详情
hdu1430魔板(代码片段)
...靡全球之后不久,Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成,每个方块颜色均不相同,可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示:从魔板的左上角开始,按顺时针方向... 查看详情
[bzoj1331]魔板(代码片段)
...发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:|1|2|3|4||-|-|-|-||8|7|6|5|我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一... 查看详情
xmu1016magicsquare幻方构造
题目链接:http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1016题目大意:给你一个整数N,然后输出一个N阶幻方。解题思路:关于幻方。搜索肯定超时。可是我们能够直接构造一个幻方。就是依据奇数阶(2*M+1)幻方、单偶数阶(4*M+2)幻方、双... 查看详情
luogu1275魔板(代码片段)
https://zybuluo.com/ysner/note/1136271题面有这样一种魔板:它是一个长方形的面板,被划分成\(n\)行\(m\)列的\(n*m\)个方格。每个方格内有一个小灯泡,灯泡的状态有两种(亮或暗)。我们可以通过若干操作使魔板从一个状态改变为另一个状... 查看详情
jenkins邮件通知html魔板
<!DOCTYPEhtml><html><head><metacharset="UTF-8"><title>${ENV,var="JOB_NAME"}-第${BUILD_NUMBER}次构建日志</title></head><bodyleftmargin="8"marginwidth="0"topmargin 查看详情
hdu1430魔板(康托展开+bfs+预处理)
魔板TimeLimit:10000/5000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):2921 AcceptedSubmission(s):649 ProblemDescription 在魔方风靡全球之后不 查看详情
bfs魔板(代码片段)
...难,但我们也要一直走下去🎈题目链接思路:因为魔板只要三种移动的方式,我们可以逐层进行枚举,相当于对一颗三叉树进行BFS遍历(一层一层 查看详情
魔板问题(搜索)(代码片段)
问题E:【搜索】魔板问题时间限制:1Sec 内存限制:64MB提交:23 解决:6[提交][状态][讨论版][命题人:admin]题目描述据说能使持有者成为世界之主的上古神器隐藏在魔板空间,魔板由8个同样大小的方块组成,每个方块颜... 查看详情
hdu-1430-魔板(康托展开+bfs预处理)(代码片段)
魔板TimeLimit:10000/5000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):4242 AcceptedSubmission(s):1011ProblemDescription在魔方风靡全球之后不久 查看详情