程序员人生 网站导航

hdu1430 (bfs)

栏目:php教程时间:2016-03-16 08:49:17

魔板

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2398 Accepted Submission(s): 504


Problem Description
在魔方风行全球以后不久,Rubik先生发明了它的简化版――魔板。魔板由8个一样大小的方块组成,每一个方块色彩均不相同,可用数字1⑻分别表示。任1时刻魔板的状态可用方块的色彩序列表示:从魔板的左上角开始,按顺时针方向顺次写下各方块的色彩代号,所得到的数字序列便可表示此时魔板的状态。例如,序列(1,2,3,4,5,6,7,8)表示魔板状态为:

1 2 3 4
8 7 6 5

对魔板,可施加3种不同的操作,具体操作方法以下:

A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移1格,如上图可变换为41236785
C: 中间4个方块顺时针旋转1格,如上图可变换为17245368

给你魔板的初始状态与目标状态,请给出由初态到目态变换数最少的变换步骤,若有多种变换方案则取字典序最小的那种。

Input
每组测试数据包括两行,分别代表魔板的初态与目态。

Output
对每组测试数据输出满足题意的变换步骤。

Sample Input
12345678 17245368 12345678 82754631

Sample Output
C AC

Author
LL

Source
ACM暑期集训队练习赛(3)  

分析:题目本身难度还行,主要就是标记麻烦,这就得用到1个新知识,康拓展开这里戳1下你就知道;然后预处理,对每一个情况都可以看成“12345678”转化为另外一个情况,这就值用bfs1次,不用每次都去bfs1遍,可以省下大量时间。

#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e⑹; const double pi = acos(⑴.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; #define ll long long #define CL(a) memset(a,0,sizeof(a)) string s,t,dp[50005]; int vis[50005]; int func[11],pos[11]; struct node { int va; string str,ans; }; int Hash(string &s)//康拓展开 { int va=0; for(int i=0;i<7;i++) { int cnt=0; for(int j=i+1;j<8;j++) if(s[j]<s[i]) cnt++; va+=cnt*func[7-i]; } return va; } void goto1(string &s)//下面是3种操作 { for(int i=0; i<4; i++) swap(s[i], s[i+4]); } void goto2(string &s) { char ff=s[3],dd=s[7]; for(int i=2; i>=0; i--) s[i+1]=s[i]; s[0]=ff; for(int i=6; i>=4; i--) s[i+1]=s[i]; s[4]=dd; } void goto3(string &s) { char ff=s[1]; s[1]=s[5]; s[5]=s[6]; s[6]=s[2]; s[2]=ff; } void bfs() { CL(vis); node now,next; queue<node> q; now.str=s; now.ans=""; now.va=Hash(s); vis[now.va]=1; dp[now.va]=""; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); string t=now.str; goto1(t); int k=Hash(t); if(!vis[k]) { next.str=t; vis[k]=1; next.ans=now.ans+'A'; next.va=k; dp[k]=next.ans; q.push(next); } t=now.str; goto2(t); k=Hash(t); if(!vis[k]) { next.str=t; vis[k]=1; next.ans=now.ans+'B'; next.va=k; dp[k]=next.ans; q.push(next); } t=now.str; goto3(t); k=Hash(t); if(!vis[k]) { next.str=t; vis[k]=1; next.ans=now.ans+'C'; next.va=k; dp[k]=next.ans; q.push(next); } } } int main() { func[0]=1; for(int i=1;i<=9;i++) func[i]=func[i⑴]*i; s="12345678"; bfs(); while(cin>>s>>t) { swap(s[4], s[7]); swap(s[5], s[6]); swap(t[4], t[7]); swap(t[5], t[6]); for(int i=0; i<8; i++) pos[s[i]-'0']=i+1; for(int i=0; i<8; i++)//置换成“13245678”转化为另外一个串 t[i]=pos[t[i]-'0']; int k=Hash(t); cout<<dp[k]<<endl; } return 0; }


版权声明:本文为博主原创文章,未经博主允许不得转载。

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐