程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1430 （bfs）

hdu1430 （bfs）

編輯：C++入門知識

hdu1430 （bfs）

魔板

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-8分別表示。任一時刻魔板的狀態可用方塊的顏色序列表示：從魔板的左上角開始，按順時針方向依次寫下各方塊的顏色代號，所得到的數字序列即可表示此時魔板的狀態。例如，序列(1,2,3,4,5,6,7,8)表示魔板狀態為：

1 2 3 4
8 7 6 5

對於魔板，可施加三種不同的操作，具體操作方法如下：

A: 上下兩行互換,如上圖可變換為狀態87654321
B: 每行同時循環右移一格,如上圖可變換為41236785
C: 中間4個方塊順時針旋轉一格,如上圖可變換為17245368

給你魔板的初始狀態與目標狀態，請給出由初態到目態變換數最少的變換步驟，若有多種變換方案則取字典序最小的那種。

Input 每組測試數據包括兩行，分別代表魔板的初態與目態。

Output 對每組測試數據輸出滿足題意的變換步驟。

Sample Input

Sample Output

C
AC

Author LL
Source ACM暑期集訓隊練習賽（三）
分析：題目本身難度還行，主要就是標記麻煩，這就得用到一個新知識，康拓展開這裡戳一下你就知道；然後預處理，對於每個情況都可以看成“12345678”轉化為另一個情況，這就值用bfs一次，不用每次都去bfs一遍，可以省下大量時間。

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.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]=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 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-1]*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<