首页 > 代码库 > BFS [HDU 1430] 魔板
BFS [HDU 1430] 魔板
魔板
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1917 Accepted Submission(s): 393
Problem Description
在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：
1 2 3 4
8 7 6 5
对于魔板，可施加三种不同的操作，具体操作方法如下：
A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
1 2 3 4
8 7 6 5
对于魔板，可施加三种不同的操作，具体操作方法如下：
A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
Input
每组测试数据包括两行，分别代表魔板的初态与目态。
Output
对每组测试数据输出满足题意的变换步骤。
Sample Input
12345678172453681234567882754631
Sample Output
CAC
受不了、、WA了好久、结果映射写错了
这题 - -、最开始直接暴力BFS、这肯定超时啊、知道超时可是还是交了一下、好吧、超内存
这不重要、没标记的原因、加上康托展开、超时
好吧、百度下、和八数码问题一样，先把所有情况的答案算出来，但是要有统一起点，所以讲A到B转换为12345678到C、
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <map>#include <string>using namespace std;#define N 326888bool vis[N];string dp[N];int fac[]={1,1,2,6,24,120,720,5040,40320,326880};struct node{ string s; string op;};int Hash(string &s) { int i,j,res=0; bool has[10]={0}; for(i=0;i<9;i++) { int x=s[i]-‘0‘,y=0; for(j=1;j<x;j++) { if(!has[j]) y++; } res+=y*fac[8-i]; has[x]=1; } return res+1;}void BFS(){ int i,j; node now,next; queue<node> q; memset(vis,0,sizeof(vis)); now.s="12345678"; now.op=""; q.push(now); vis[Hash(now.s)]=1; while(!q.empty()) { now=q.front(); q.pop(); dp[Hash(now.s)]=now.op; for(int i=1;i<=3;i++) { next=now; if(i==1) { next.op+=‘A‘; swap(next.s[0],next.s[7]); swap(next.s[1],next.s[6]); swap(next.s[2],next.s[5]); swap(next.s[3],next.s[4]); } else if(i==2) { next.op+=‘B‘; char ch=next.s[3]; for(j=3;j>=1;j--) next.s[j]=next.s[j-1]; next.s[0]=ch; ch=next.s[4]; for(j=4;j<7;j++) next.s[j]=next.s[j+1]; next.s[7]=ch; } else { next.op+=‘C‘; char ch=next.s[1]; next.s[1]=next.s[6]; next.s[6]=next.s[5]; next.s[5]=next.s[2]; next.s[2]=ch; } if(!vis[Hash(next.s)]) { vis[Hash(next.s)]=1; q.push(next); } } }}int main(){ BFS(); string s1,s2; while(cin>>s1>>s2) { map<char,char> mp; for(int i=0;i<8;i++) //好吧、这儿写反了，WA- - { mp[s1[i]]=i+1+‘0‘; } for(int i=0;i<8;i++) { s2[i]=mp[s2[i]]; } cout<<dp[Hash(s2)]<<endl; } return 0;}
BFS [HDU 1430] 魔板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。