ssl1692-魔闆【HSAH,bfs】

前言

好的，首先說明一下，這裡用的是字元串的方法。根據c++字元串的尿性，速度比較慢，當然也可以改成字元數組，隻不過我比較懶（沒錯╭(╯^╰)╮）

正題

有個2*4的矩陣被稱為魔闆，有三種操作

“A”：交換上下兩行；

“B”：将最右邊的一列插入最左邊；

“C”：魔闆中央四格作順時針旋轉。

然後初始狀态是

1 2 3 4

8 7 6 5

然後嘞，就是嘞

給出一個狀态，要求改變到那個狀态。

輸入輸出（建議無視）

Input

隻有一行，包括8個整數，用空格分開（這些整數在範圍 1——8 之間），表示目标狀态。

Output

Line 1: 包括一個整數，表示最短操作序列的長度。

Line 2: 在字典序中最早出現的操作序列，用字元串表示，除最後一行外，每行輸出60個字元。

Sample Input

2 6 8 4 5 7 3 1

Sample Output

7

BCABCCB

解題思路

這道題就是得把一塊闆線性化，然後找出變化規律。然後用哈希來判斷重複優化廣搜。

将線性化之後的版轉換為數字，然後存進哈希表裡判斷重複。

代碼

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int ruler[][]={{,,,,,,,},{,,,,,,,},{,,,,,,,}};
//變化公式
string state[];//狀态
string hash[],ss;//哈希表
int head,tail,z,x,father[],num[];
char dot[];
int hashm(string s)//哈希表
{
    int w=;
    for (int i=;i<;i++)
    {
        w=w*+s[i]-;
    }//轉成數字
    w%=;//哈希函數
    int i=;
    while (i< && hash[(w+i)%]!="" && hash[(w+i)%]!=s)
      i++;//定位
    if (hash[(w+i)%]=="")//如果找到空位
    {
        hash[(w+i)%]=s;//記錄
        return false;
    }
    else return true;//放回找到
}
void bfs()
{   
    hashm("12345678");//記錄狀态
    head=;tail=;
    state[]="12345678";//狀态記錄
    do
    {
        head++;//出隊
        for (int i=;i<;i++)
        {
            tail++;//入隊
            father[tail]=head;//記錄上一個
            state[tail]="";//狀态為空
            num[tail]=num[head]+;//記錄改變次數
            if (i==) dot[tail]='A';
            if (i==) dot[tail]='B';
            if (i==) dot[tail]='C';//記錄操作
            for (int j=;j<;j++)
            {
              state[tail]+=state[head][ruler[i][j]-];
              //變化狀态
            }
            if (hashm(state[tail])) tail--;//拒絕入隊
            else if (state[tail]==ss) return;//找到退出
        }
    }
    while(head<tail);
}
void print(int x)
{
    if (x==) return;
    print(father[x]);//傳回
    printf("%c",dot[x]);//輸出
}
int main()
{
    for (int i=;i<;i++)
    {
        scanf("%d",&x);
        ss+=x+;//字元串
    }
    if (ss=="12345678") printf("0");//特殊判斷
    else
    {
        bfs();//廣搜
        printf("%d\n",num[tail]);//輸出
        print(tail);//輸出操作
    }
}
           

轉載于:https://www.cnblogs.com/sslwyc/p/9218584.html