HDU - 1043 Eight (8 수 코드) 역방향 BFS + 강 탁 전개 hash 판정 + 타 표

HDU - 1043 Eight (8 수 코드) 역방향 BFS + 강 탁 전개 hash 판정 + 타 표
강 탁 전개
강 타 쿠 가 펼 친 것 을 이해 하지 못 하면 배 워 보 세 요.https://blog.csdn.net/laaahu/article/details/96425860
제목:
9 개의 격자 중에서 각 격자 에 하나의 숫자 가 있 는데 그 중 하 나 는 x (뒤에 우 리 는 0 으로 이 점 을 표시 합 니 다) 이기 때문에 0 에서 8 이라는 9 개의 숫자 는 하나의 3X3 의 격자 에서 운동 합 니 다. 매번 x 와 인접 한 상하 좌우 의 숫자 는 교환 할 수 있 습 니 다. 요구 하 는 것 은 하나의 격자 의 상태 에 최종 적 으로 1, 2, 3, 4, 5, 6, 7, 8 x 에 이 를 수 있 는 지 판단 하 는 것 입 니 다.작업 단계 u (위), d (아래), l (왼쪽), r (오른쪽) 를 출력 할 수 있다 면
생각:
광 수 를 생각 하 실 수도 있 지만 직접 광 수 상태 가 너무 많 으 면 시간 을 초과 할 것 입 니 다. 그래서 우 리 는 강 탁 이 전개 하 는 것 을 배 운 후에 이것 이 전체 배열 의 문제 라 고 생각 하기 쉽 습 니 다. 우 리 는 강 탁 을 이용 하여 hash 함수 판 중 을 구축 하 는 것 이 시간 을 크게 단축 시 킬 수 있 습 니 다.시 계 를 치 는 것 은 여러 그룹 이 입력 하면 bfs 를 한 번 만 진행 하고 모든 결 과 를 얻 으 면 어느 정도 시간 을 절약 할 수 있 기 때문이다.구체 적 인 세부 사항 은 코드 주석 을 볼 수 있 습 니 다.그리고 나 는 줄곧 메모 리 를 초 과 했 어. 너의 모든 상 태 를 저장 하지 마. 필요 없어. 이것 이 바로 내 가 왜 메모 리 를 초 과 했 는 지.하나의 배열 만 저장 해도 상태 가 충분 하 다.
AC 코드:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=362885;
const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};    //        0~9   。
bool vis[maxn];
int go[8]={1,0,-1,0,0,1,0,-1};      //      
char index[5]="udlr";               //             ，         
int aim=46234;                      //    123456780 hash 。
string path[maxn];                  //    
int state[9];                       //      
struct node{
    int hash;
    int lac;     //0   
    string path;
};
int cantor(int a[]){                //       
    int x=0;
    for(int i=0;i<9;i++){
        int small=0;
        for(int j=i+1;j<9;j++){
            if(a[j]<a[i])small++;
        }
        x+=small*fac[9-i-1];
    }
    return x+1;
}
void recantor(int *a,int val){     //                      
    vector<int>vv;
    for(int i=0;i<9;i++){
        vv.push_back(i);
    }
    for(int i=0;i<9;i++){
        int r,s;
        r=val/fac[9-i-1];
        s=val%fac[9-i-1];
        val=s;
        sort(vv.begin(),vv.end());
        a[i]=vv[r];
        vv.erase(vv.begin()+r);
    }
}
void bfs(){
    memset(vis,false,sizeof(vis));
    queue<node>q;
    node now,temp;
    for(int i=0;i<8;i++)state[i]=i+1;
    state[8]=0;
    now.lac=8;
    now.hash=aim;
    now.path="";
    path[aim]="";
    q.push(now);
    vis[aim]=true;
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0;i<8;i+=2){
            int xx=now.lac/3+go[i];
            int yy=now.lac%3+go[i+1];
            if(xx>=0&&xx<=2&&yy>=0&&yy<=2){
                temp=now;
                temp.lac=xx*3+yy;
                recantor(state,now.hash-1);   //         ，  state    。
                swap(state[temp.lac],state[now.lac]);   //      
                temp.hash=cantor(state);           //        hash 
                if(!vis[temp.hash]){
                    vis[temp.hash]=true;
                    temp.path=index[i/2]+temp.path;
                    q.push(temp);
                    path[temp.hash]=temp.path;
                }
            }
        }
    }
    return ;
}
int main()
{
    node cur;
    bfs();  //    。
    char s;
    while(cin>>s){
        if(s=='x'){
            cur.lac=0;
            state[0]=0;
            for(int i=1;i<=8;i++){
                cin>>s;
                state[i]=s-'0';
            }
        }
        else{
            state[0]=s-'0';
            for(int i=1;i<=8;i++){
                cin>>s;
                if(s=='x'){
                    state[i]=0;
                    cur.lac=i;
                }
                else{
                    state[i]=s-'0';
                }
            }
        }
        cur.hash=cantor(state);
        if(!vis[cur.hash])cout<<"unsolvable"<<endl;
        else{
            cout<<path[cur.hash]<<endl;
        }
    }
    return 0;
}