hdu1430 （bfs）
來源：程序員人生 發布時間：2016-03-16 08:49:17 閱讀次數：3056次
魔板
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
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;
}
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
