启发式搜索求助
  • 板块P5507 机关
  • 楼主小超手123
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/1/31 16:29
  • 上次更新2023/10/24 02:21:57
查看原帖
启发式搜索求助
490978
小超手123楼主2023/1/31 16:29
#include<bits/stdc++.h>
#define int long long
using namespace std;
int mov[20][5],Pow[20],nxt[20];
bool vis[100000008];
struct node{
    int a[20],g,h,f; //f=g+h
    bool operator<(const node &y) const{
        return f>y.f;
    }
};
priority_queue<node>Q;
int get_h(int a[]){
    int num=0;
    for(int i=1;i<=12;i++){
        if(a[i]==1)num+=0;
        if(a[i]==2)num+=3;
        if(a[i]==3)num+=2;
        if(a[i]==4)num+=1;
    }
    num/=4;
    return num;
}
int change(int a[]){
    int num=0;
    for(int i=1;i<=12;i++)
        num+=a[i]*Pow[i]; //转成一个4进制数
    return num;
}
signed main(){
    Pow[0]=1;
    for(int i=1;i<=15;i++)
        Pow[i]=Pow[i-1]*4;
    node Start;
    for(int i=1;i<=12;i++){
        cin>>Start.a[i];
        for(int j=1;j<=4;j++)
            cin>>mov[i][j];
    }
    Start.g=0;
    Start.h=get_h(Start.a);
    Start.f=Start.g+Start.h;
    Q.push(Start);
    vis[change(Start.a)]=1;
    while(!Q.empty()){
        node cmp=Q.top();
        /*for(int i=1;i<=12;i++)cout<<cmp.a[i];
        cout<<"->"<<change(cmp.a);
        cout<<endl;*/
        vis[change(cmp.a)]=1;
        Q.pop();
        for(int i=1;i<=12;i++){ //枚举转动哪个按钮
            for(int j=1;j<=12;j++)
                nxt[j]=cmp.a[j];

            nxt[mov[i][nxt[i]]]++;  //带动其他按钮旋转一次
            if(nxt[mov[i][nxt[i]]]==5)
                nxt[mov[i][nxt[i]]]++; 

            nxt[i]++; //自身旋转一次  
            if(nxt[i]==5)
                nxt[i]=1;

            if(vis[change(nxt)])
                continue; //如果此状态遍历过,就不要
            node p;
            for(int j=1;j<=12;j++)
                p.a[j]=nxt[j];
            p.g=cmp.g+1;
            p.h=get_h(nxt);
            p.f=p.g+p.h; 
            Q.push(p);
            bool f=1;
            for(int i=1;i<=12;i++)
                if(nxt[i]!=1){
                    f=0;
                    break;
                }
            if(f==1){
                cout<<cmp.g+1;
                return 0;
            }
        }
    }
    return 0;
}
2023/1/31 16:29
加载中...