[HAOI2008]移动玩具
Posted on 2015年1月17日 16:561 2 3 4 5 6 7 | /****************************************\* Author : ztx* Title : [HAOI2008]移动玩具* ALG : 搜索 + hash剪枝* CMT :* Time :\****************************************/ |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | /****************************************\* Author : ztx* Title : [HAOI2008]移动玩具* ALG : 搜索 + hash剪枝* CMT :* Time :\****************************************/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;#define maxs 65536LLconst 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 ;} |