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