ztx's Blog

/****************************************\
* Author : ztx
* Title  : [HAOI2008]移动玩具
* ALG    : 搜索 + hash剪枝
* CMT    :
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HAOI2008]移动玩具
* ALG    : 搜索 + hash剪枝
* CMT    :
* Time   :
\****************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

#define  maxs  65536LL

const int dx[4] = {0 , 0 , 1 , -1} ,
          dy[4] = {1 , -1 , 0 , 0} ;

struct data { bool a[5][5] ; int step ; } q[maxs] ;

int Start , End , h ;
bool ans[5][5] , exist[maxs] ;

int hash(bool a[5][5]) {
    int k = 1 , s = 0 , i , j ;
    for (i = 1 ; i < 5 ; i ++ )
        for (j = 1 ; j < 5 ;j ++ )
            s += k*a[i][j] , k <<= 1 ;
    return s ;
}

int main() {
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    int t = 0 , w = 1 , i , j , k , x , y ;
    char ch[5] ;
    for (i = 1 ; i < 5 ; i ++ ) {
        scanf("%s", ch) ;
        for(j = 1 ; j <= 4 ; j ++ )
           q[0].a[i][j] = ch[j-1]-'0' ;
    }
    for(i = 1 ; i <= 4 ; i ++ ) {
        scanf("%s",ch);
        for(j = 1 ; j <= 4 ; j ++ )
           ans[i][j] = ch[j-1]-'0' ;
    }
    Start = hash(q[t].a) ;
    End = hash(ans) ;
    if (Start == End) {
        puts("0") ; goto END ;
    }
    exist[Start] = 1 ;
    while (t < w) {
        for(i = 1 ; i < 5 ; i ++ )
            for (j = 1 ; j < 5 ; j ++ ) if (q[t].a[i][j])
                for (k = 0 ; k < 4 ; k ++ ) {
                    x = i+dx[k] , y = j+dy[k] ;
                    if (q[t].a[x][y] || x>4 || y>4 || x<1 || y<1) continue ;
                    swap(q[t].a[i][j] , q[t].a[x][y]) ;
                    h = hash(q[t].a) ;
                    if (!exist[h]) {
                        if (h == End) {
                            printf("%d", q[t].step+1) ; goto END ;
                        }
                        exist[h] = 1 ;
                        memcpy(q[w].a , q[t].a , sizeof q[w].a) ;
                        q[w].step = q[t].step+1 ;
                        w ++ ;
                    }
                    swap(q[t].a[i][j] , q[t].a[x][y]) ;
                }
        t ++ ;
    }
    END : ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}