問題 D: 【寬搜入門】魔闆

【寬搜入門】魔闆

時間限制: 1 Sec 記憶體限制: 128 MB

題目描述

在成功地發明了魔方之後，魯比克先生發明了它的二維版本，稱作魔闆。這是一張有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個字元。

Sample Input

2 6 8 4 5 7 3 1

Sample Output

7

BCABCCB

這題按理來說不算難題卻卡了我好久。查重很關鍵，不然會逾時。本來想用map< int[2][4], bool> Hash 來标記每個情形，後來發現我想多了，數組應該是不能作為鍵的，是以隻好把每種情形轉換成一個int。這方法看起來挺笨的，可能有更好的辦法吧。還有有多組資料需要注意一下。另外我忘記了處理原封不動即步數為0的情況，卡在錯誤12%好久。。。

C++代碼如下。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int matrix[][] = {{, , , }, {, , , }};
int final[][];
struct node{
    int M[][];  //進行目前操作後的魔闆
    vector<char> bef;  //進行目前操作後的總操作步驟
} Node;
bool same(int a[][]){
    for(int i = ; i < ; i++){
        for(int j = ; j < ; j++){
            if(a[i][j] != final[i][j])
                return false;
        }
    }
    return true;
}
bool Hash[] = {false};
int conv(int a[][]){ //八進制轉十進制
    int b[];
    for(int i = ; i < ; i++){
        b[i] = a[][i] - ;
    }
    for(int i = ; i < ; i++){
        b[i] = a[][i - ] - ;
    }
    int num = ;
    for(int i = ; i < ; i++){
        num = num *  + b[i];
    }
    return num;
}
void BFS(){
    queue<node> Q;
    for(int i = ; i < ; i++){
        for(int j = ; j < ; j++){
            Node.M[i][j] = matrix[i][j];
        }
    }
    if(same(Node.M)){   //如果在這不判斷，原封不動的結果會是：操作AA，步數為2
        cout << '0' << endl;
        cout << endl;
        return ;    
    }
    Q.push(Node);
    while(!Q.empty()){
        node top = Q.front();
        Q.pop();
        //A
        for(int i = ; i < ; i++){
            for(int j = ; j < ; j++){
                Node.M[i][j] = top.M[ - i][j];
            }
        }
        if(!Hash[conv(Node.M)]){
            Hash[conv(Node.M)] = true;
            Node.bef = top.bef;
            Node.bef.push_back('A');
            if(same(Node.M)){
                cout << Node.bef.size() << endl;
                for(int i =  ; i < Node.bef.size(); i++){
                    if(i >  && i %  == )
                        cout << endl;
                    cout << Node.bef[i];
                }
                Node.bef.clear();// 不清空會導緻下一組資料是接在前一組後面的，下面BC同理
                cout << endl;
                return;
            }               
            Q.push(Node);
        }           
        //B
        for(int i = ; i < ; i++){
            for(int j = ; j < ; j++){
                Node.M[i][j] = top.M[i][j - ];             
            }
        }
        Node.M[][] = top.M[][];
        Node.M[][] = top.M[][];     
        if(!Hash[conv(Node.M)]) {   
            Hash[conv(Node.M)] = true;
            Node.bef = top.bef; 
            Node.bef.push_back('B');
            if(same(Node.M)){
                cout << Node.bef.size() << endl;
                for(int i =  ; i < Node.bef.size(); i++){
                    if(i >  && i %  == )
                        cout << endl;
                    cout << Node.bef[i];
                }
                Node.bef.clear();
                cout << endl;
                return;
            }           
            Q.push(Node);
        }       
        //C
        for(int i = ; i < ; i++){
            for(int j = ; j < ; j++){
                Node.M[i][j] = top.M[i][j];             
            }
        }
        Node.M[][] = top.M[][];
        Node.M[][] = top.M[][];
        Node.M[][] = top.M[][];
        Node.M[][] = top.M[][]; 
        if(!Hash[conv(Node.M)]){
            Hash[conv(Node.M)] = true;
            Node.bef = top.bef;
            Node.bef.push_back('C');            
            if(same(Node.M)){
                cout << Node.bef.size() << endl;
                for(int i =  ; i < Node.bef.size(); i++){
                    if(i >  && i %  == )
                        cout << endl;
                    cout << Node.bef[i];
                }
                Node.bef.clear();
                cout << endl;
                return;
            }           
            Q.push(Node);
        }       
    }
}
int main(){
    while(cin >> final[][]){
        for(int i = ; i < ; i++){
            Hash[i] = false;
        }
        for(int i = ; i < ; i++){
            cin >> final[][i];
        }
        for(int i = ; i < ; i++){
            cin >> final[][ - i];
        }
        BFS();
    }

    return ;
}
/**************************************************************
    Problem: 5998
    User: 14041045
    Language: C++
    Result: 正确
    Time:104 ms
    Memory:18680 kb
****************************************************************/